{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Substrings With Only 1s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numSub"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #仅含 1 的子串数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二进制字符串 <code>s</code>（仅由 &#39;0&#39; 和 &#39;1&#39; 组成的字符串）。</p>\n",
    "\n",
    "<p>返回所有字符都为 1 的子字符串的数目。</p>\n",
    "\n",
    "<p>由于答案可能很大，请你将它对 10^9 + 7 取模后返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;0110111&quot;\n",
    "<strong>输出</strong>：9\n",
    "<strong>解释：</strong>共有 9 个子字符串仅由 &#39;1&#39; 组成\n",
    "&quot;1&quot; -&gt; 5 次\n",
    "&quot;11&quot; -&gt; 3 次\n",
    "&quot;111&quot; -&gt; 1 次</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;101&quot;\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>子字符串 &quot;1&quot; 在 s 中共出现 2 次\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;111111&quot;\n",
    "<strong>输出：</strong>21\n",
    "<strong>解释：</strong>每个子字符串都仅由 &#39;1&#39; 组成\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;000&quot;\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>s[i] == &#39;0&#39;</code> 或 <code>s[i] == &#39;1&#39;</code></li>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10^5</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-substrings-with-only-1s](https://leetcode.cn/problems/number-of-substrings-with-only-1s/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-substrings-with-only-1s](https://leetcode.cn/problems/number-of-substrings-with-only-1s/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"0110111\"', '\"101\"', '\"111111\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        res = 0\n",
    "        last2 = last1 = -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if left <= x <= right:\n",
    "                last1 = i\n",
    "            elif x > right:\n",
    "                last2 = i\n",
    "                last1 = -1\n",
    "            if last1 != -1:\n",
    "                res += last1 - last2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], a: int, b: int) -> int:\n",
    "        n,ans=len(nums),0\n",
    "        j,k=-1,-1\n",
    "        for i in range(n):\n",
    "            if nums[i]>b:\n",
    "                k=i\n",
    "            else:\n",
    "                if nums[i]<a:\n",
    "                    ans+=j-k if j>k else 0\n",
    "                else:\n",
    "                    ans+=i-k\n",
    "                    j=i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans,slow,fast = 0,-1,-1\n",
    "        for idx,i in enumerate(nums):\n",
    "            if i > right:\n",
    "                slow = idx\n",
    "            if i >= left:\n",
    "                fast = idx\n",
    "            ans += fast -slow\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        res = 0\n",
    "        last2 = last1 = -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if left <= x <= right:\n",
    "                last1 = i\n",
    "            elif x > right:\n",
    "                last2 = i\n",
    "                last1 = -1\n",
    "            if last1 != -1:\n",
    "                res += last1 - last2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        j, temp, ans = -1, 0, 0\n",
    "        for i in range(n):\n",
    "            if nums[i] > right:\n",
    "                j = i\n",
    "            if nums[i] >= left:\n",
    "                temp = i - j\n",
    "\n",
    "            ans += temp\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        ans = 0\n",
    "        last1 = -1\n",
    "        last2 = -1\n",
    "        for i in range(len(nums)):\n",
    "            if left <= nums[i] and nums[i] <= right:\n",
    "                last1 = i\n",
    "            elif nums[i] > right:\n",
    "                last1 = -1\n",
    "                last2 = i # last invalid\n",
    "            if last1 != -1:\n",
    "                ans += last1 - last2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        ans = 0\n",
    "        end_index = start_index = -1\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] > right:\n",
    "                end_index = start_index = i\n",
    "            else:\n",
    "                if left <= nums[i] <= right:\n",
    "                    end_index = i\n",
    "                ans += (end_index - start_index)\n",
    "        return ans\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        def calculate(nums, k):\n",
    "            i = j = ret = 0\n",
    "            n = len(nums)\n",
    "            while i < n:\n",
    "                if nums[i] > k:\n",
    "                    j = i + 1\n",
    "                ret += i - j + 1\n",
    "                i += 1\n",
    "            return ret\n",
    "        return calculate(nums, right) - calculate(nums, left - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        last1, last2, ans = -1, -1, 0\n",
    "        for i in range(len(nums)):\n",
    "            if left <= nums[i] <= right:\n",
    "                last2 = i\n",
    "            elif nums[i] > right:\n",
    "                last1 = i\n",
    "                last2 = -1\n",
    "            if last2 != -1:\n",
    "                ans += last2 - last1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        ans, i0, i1 = 0, -1, -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if x > right: i0 = i\n",
    "            if x >= left: i1 = i\n",
    "            ans += i1 - i0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        ans,i0,i1=0,-1,-1\n",
    "        for i,x in enumerate(nums):\n",
    "            if x>right:i0=i\n",
    "            if x>=left:i1=i\n",
    "            ans+=i1-i0\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        ret = 0\n",
    "        last1 = last2 = -1\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < left:\n",
    "                if last1 > last2:\n",
    "                    ret += last1 - last2\n",
    "            elif nums[i] > right:\n",
    "                last2 = i\n",
    "            else:\n",
    "                last1 = i\n",
    "                ret += last1 - last2\n",
    "            if ret < 0:\n",
    "                print(\"debug\")\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0]*n\n",
    "        i,j,k = 0,0,0\n",
    "        while j < n:\n",
    "            if nums[j] < left:\n",
    "                dp[j] += dp[k]\n",
    "            elif nums[j] > right:\n",
    "                i = j+1\n",
    "                k = j+1\n",
    "            else:\n",
    "                dp[j] = j-i+1\n",
    "                k = j\n",
    "            j += 1\n",
    "        return sum(dp)\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func1(t):\n",
    "    res = 0\n",
    "\n",
    "def func(x, left, right):\n",
    "    res = 0\n",
    "    n = len(x)\n",
    "    for i in range(n):\n",
    "        if x[i] < left:\n",
    "            if i + 1 != n:\n",
    "                for j in range(i+1,n):\n",
    "                    if x[j] >= left:\n",
    "                        res += n -j\n",
    "                        break\n",
    "        else:\n",
    "            res += n - i\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        i = 0\n",
    "        j = 0\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        maxNumber = left - 1\n",
    "        while j < n:\n",
    "            if nums[j] >= left and nums[j] <= right:\n",
    "                maxNumber = max(maxNumber, nums[j])\n",
    "                j += 1\n",
    "            elif maxNumber >= nums[j]:\n",
    "                j += 1\n",
    "            else:\n",
    "                if i != j:\n",
    "                    res.append(nums[i:j])\n",
    "                j += 1\n",
    "                i = j\n",
    "                maxNumber = left - 1\n",
    "        if i != j:\n",
    "            res.append(nums[i:j])\n",
    "        a = 0\n",
    "        print(res)\n",
    "        for i in res:\n",
    "            a += func(i, left, right)\n",
    "        return a            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] *n\n",
    "        if left <= nums[0] and nums[0] <= right:\n",
    "            dp[0] = 1\n",
    "        for i in range(1,n):\n",
    "            if nums[i] >= left and nums[i] <= right:                \n",
    "                x = 0\n",
    "                j = i - 1\n",
    "                while j >= 0 and nums[j] < left:                    \n",
    "                        x += 1\n",
    "                        j -= 1\n",
    "                dp[i] = dp[i-1] + 1 + x\n",
    "            elif nums[i] < left:\n",
    "                for j in range(i-1, -1, -1):\n",
    "                    #print(i, j, nums[j])\n",
    "                    if nums[j] >= left:\n",
    "                        dp[i] = dp[j]\n",
    "                        break\n",
    "        #print(dp)\n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        n = len(nums)\n",
    "        dp = [0 for _ in range(n)]\n",
    "        temp = 0\n",
    "        if left <= nums[0] <= right:\n",
    "            dp[0] = 1\n",
    "        if nums[0] < left:\n",
    "            temp = 1\n",
    "        if n <= 1:\n",
    "            return dp[0] \n",
    "        for i in range(1,n):\n",
    "            if nums[i] < left:\n",
    "                dp[i] = dp[i-1]\n",
    "                temp += 1\n",
    "            elif nums[i] > right:\n",
    "                dp[i] = 0\n",
    "                temp = 0\n",
    "            else:\n",
    "                dp[i] = dp[i-1] + temp + 1\n",
    "                temp = 0\n",
    "        return sum(dp)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        l, r = [-1] * n, [n] * n\n",
    "        stk = []\n",
    "        for i, v in enumerate(nums):\n",
    "            while stk and nums[stk[-1]] <= v:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                l[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stk and nums[stk[-1]] < nums[i]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                r[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        return sum((i - l[i]) * (r[i] - i) for i, v in enumerate(nums) if left <= v <= right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], l: int, r: int) -> int:\n",
    "        n=len(nums)\n",
    "        left,right=[-1]*n,[n]*n\n",
    "        q=deque()\n",
    "        for i in range(n):\n",
    "            while q and nums[q[-1]]<=nums[i]:\n",
    "                q.pop()\n",
    "            if q:\n",
    "                left[i]=q[-1]\n",
    "            q.append(i)\n",
    "        q=deque()\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while q and nums[q[-1]]<nums[i]:\n",
    "                q.pop()\n",
    "            if q:\n",
    "                right[i]=q[-1]\n",
    "            q.append(i)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            if l<=nums[i]<=r:\n",
    "                ans+=(i-left[i])*(right[i]-i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        d=[]\n",
    "        c=[]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]>right:\n",
    "                d.append(i)\n",
    "            if nums[i]>=left:\n",
    "                c.append(i)\n",
    "        s=0\n",
    "        def j(a):\n",
    "            return a*(a+1)/2\n",
    "        if d==[]:\n",
    "            s+=j(len(nums))\n",
    "        else:\n",
    "            s+=j(d[0])\n",
    "            for i in range(1,len(d)):\n",
    "                s+=j(d[i]-d[i-1]-1)\n",
    "            s+=j(len(nums)-1-d[-1])\n",
    "        if c==[]:\n",
    "            return int(s)\n",
    "        else:\n",
    "            s-=j(c[0])\n",
    "            for i in range(1,len(c)):\n",
    "                s-=j(c[i]-c[i-1]-1)\n",
    "            s-=j(len(nums)-1-c[-1])\n",
    "            return int(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n, res = len(nums), 0\n",
    "        l, r = [-1]*n, [n]*n\n",
    "\n",
    "        stk = []\n",
    "        for i in range(n):\n",
    "            while stk and nums[stk[-1]]<=nums[i]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                l[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        \n",
    "        stk = []\n",
    "        for i in range(n)[::-1]:\n",
    "            while stk and nums[stk[-1]]<nums[i]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                r[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "\n",
    "        for i in range(n):\n",
    "            if nums[i]>=left and nums[i]<=right:\n",
    "                res = res + (i-l[i])*(r[i]-i)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "\n",
    "        \"\"\"\n",
    "        单调栈做法, 单调栈枚举所有子区间最值为nums[i]的子区间\n",
    "\n",
    "        统计所有最大值范围在 [a, b] 之间的子数组个数，可等价为统计每一个范围落在 [a, b] 之间的 nums[i] 作为最大值时子数组的个数。\n",
    "\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "\n",
    "        # 取[lower_i, upper_i]\n",
    "        upper = [n] * n\n",
    "        lower = [-1] * n\n",
    "\n",
    "        # 单调栈统计每个元素为最大值的最大区间长度\n",
    "        st = []\n",
    "        for i, num in enumerate(nums):\n",
    "            while st and num >= nums[st[-1]]:\n",
    "                upper[st[-1]] = i\n",
    "                st.pop()\n",
    "            # //** 此处统计左侧第一个大于nums[i]的元素  **//\n",
    "            lower[i] = st[-1] if st else -1\n",
    "            st.append(i)\n",
    "\n",
    "        # 枚举最大值为 nums[i] 的所有区间\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if left <= nums[i] <= right:\n",
    "                ans += (upper[i] - i) * (i - lower[i])\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        \"\"\"\n",
    "        使用单调栈, 统计左侧第一个大于当前元素, 和右侧第一个大于等于当前元素\n",
    "\n",
    "        单调栈统计左侧第一个大于当前元素: while循环退出后的栈顶即是左侧第一个大于当前元素的位置\n",
    "            统计右侧第一个大于当前元素可以在while循环内部出栈的时候, 当前元素的位置 是 出栈元素右侧第一个大于的位置\n",
    "\n",
    "        或者采用倒序遍历的思路, 此时while循环退出时的栈顶元素即是 当前元素右侧第一个大于的位置\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "\n",
    "        l = [-1] * n\n",
    "        r = [n] * n\n",
    "\n",
    "        st = []\n",
    "        for i in range(n):\n",
    "            while st and nums[i] >= nums[st[-1]]:\n",
    "                # r[st[-1]] = i\n",
    "                st.pop()\n",
    "            # nums[l[i]] > nums[i]\n",
    "            l[i] = st[-1] if st else -1\n",
    "            st.append(i)\n",
    "\n",
    "        st = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while st and nums[i] > nums[st[-1]]:\n",
    "                st.pop()\n",
    "            # nums[r[i]] >= nums[i]\n",
    "            r[i] = st[-1] if st else n\n",
    "            st.append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if left <= nums[i] <= right:\n",
    "                ans += (i - l[i]) * (r[i] - i)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        # last2=last1=-1\n",
    "        # ans=0\n",
    "        # for i in range(len(nums)):\n",
    "        #     if left<=nums[i]<=right:\n",
    "        #         last1=i\n",
    "        #     elif nums[i]>right:\n",
    "        #         last2=i\n",
    "        #     ans+=max(0,last1-last2)\n",
    "        # return ans\n",
    "\n",
    "        stack=[]\n",
    "        n=len(nums)\n",
    "        lm,rm=[-1]*n,[n]*n\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]]<=nums[i]:\n",
    "                cur=stack.pop()\n",
    "                rm[cur]=i\n",
    "            stack.append(i)\n",
    "        stack=[]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while stack and nums[stack[-1]]<nums[i]:\n",
    "                cur=stack.pop()\n",
    "                lm[cur]=i\n",
    "            stack.append(i)\n",
    "        return sum((i-lm[i])*(rm[i]-i) for i in range(n) if left<=nums[i]<=right)\n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        l = [-1] * n\n",
    "        r = [n] * n\n",
    "        stk = []\n",
    "        for i in range(n):\n",
    "            while stk and nums[stk[-1]] <= nums[i]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                l[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stk and nums[stk[-1]] < nums[i]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                r[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if left <= nums[i] <= right:\n",
    "                ans += (i - l[i]) * (r[i] - i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "方法二：单调栈 + 枚举元素计算贡献\n",
    "\n",
    "我们还可以枚举数组中每个元素 nums[i] 作为子数组的最大值，然后统计以该元素为最大值的子数组的个数。\n",
    "问题转化为求出每个元素 nums[i] 左侧第一个大于该元素的下标 l[i]l[i]，右侧第一个大于等于该元素的下标 r[i]r[i]，\n",
    "则以该元素为最大值的子数组的个数为 (i−l[i])×(r[i]−i)。\n",
    "\n",
    "我们可以使用单调栈方便地求出 l[i]l[i] 和 r[i]r[i]\n",
    "\n",
    "时间复杂度 O(n)，空间复杂度 O(n)\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        l, r = [-1] * n, [n] * n\n",
    "        stk = []\n",
    "        for i, v in enumerate(nums):\n",
    "            while stk and nums[stk[-1]] <= v:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                l[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stk and nums[stk[-1]] < nums[i]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                r[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        return sum((i - l[i]) * (r[i] - i) for i, v in enumerate(nums) if left <= v <= right)\n",
    "\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "方法一：区间计数\n",
    "\n",
    "题目要我们统计数组 nums 中，最大值在区间 [left,right] 范围内的子数组个数。\n",
    "对于区间 [left,..right] 问题，我们可以考虑将其转换为 [0,..right] 然后再减去 [0,..left−1] 的问题。\n",
    "也就是说，所有最大元素不超过 right 的子数组个数，减去所有最大元素不超过 left−1 的子数组个数，剩下的就是最大元素在区间 [left,..right] 范围内的子数组个数。\n",
    "\n",
    "对于本题，我们只需要设计一个函数 f(x)，表示数组 nums 中，最大值不超过 x 的子数组个数。\n",
    "那么答案为 f(right)−f(left−1)。函数 f(x) 的执行逻辑如下：\n",
    "1)用变量 cnt 记录最大值不超过 x 的子数组的个数，用 t 记录当前子数组的长度。\n",
    "2)遍历数组 nums，对于每个元素 nums[i]，如果 nums[i]≤x，则当前子数组的长度加一，即 t=t+1，\n",
    "否则当前子数组的长度重置为 0，即 t=0。然后将当前子数组的长度加到 cnt 中，即cnt=cnt+t。\n",
    "3)遍历结束，将 cnt 返回即可。\n",
    "\n",
    "时间复杂度 O(n)，空间复杂度 O(1)\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        def f(x):\n",
    "            cnt = t = 0\n",
    "            for v in nums:\n",
    "                t = 0 if v > x else t + 1\n",
    "                cnt += t\n",
    "            return cnt\n",
    "\n",
    "        return f(right) - f(left - 1)\n",
    "\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n      #以i为终点的符合题目要求的个数\n",
    "        dp1 = [0] * n     #以i为终点的小于right的个数\n",
    "        ans = 0\n",
    "\n",
    "        if nums[0] <= right:\n",
    "            dp1[0] = 1\n",
    "            if nums[0] >= left:\n",
    "                dp[0] = 1\n",
    "                ans = 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if left <= nums[i] <= right:\n",
    "                dp[i] = dp1[i-1] + 1\n",
    "                dp1[i] = dp1[i-1] + 1\n",
    "            elif nums[i] < left:\n",
    "                dp[i] = dp[i-1]\n",
    "                dp1[i] = dp1[i-1] + 1\n",
    "\n",
    "            ans += dp[i]\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], l: int, r: int) -> int:\n",
    "        N = len(nums)\n",
    "        left = [-1] * N  # left[i] 为左侧严格大于 nums[i] 的最近元素位置（不存在时为-1）\n",
    "        right = [N] * N  # left[i] 为右侧大于等于 nums[i] 的最近元素位置（不存在时为 N）\n",
    "        st = []\n",
    "        for i, n in enumerate(nums):\n",
    "            while st and nums[st[-1]] <= n:\n",
    "                popi = st.pop()\n",
    "                right[popi] = i\n",
    "            left[i] = st[-1] if st else -1\n",
    "            st.append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for i, n in enumerate(nums):\n",
    "            if l <= n <= r:\n",
    "                print(left[i], i, right[i], n, (i - left[i]) * (right[i] - i))\n",
    "                ans += (i - left[i]) * (right[i] - i)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        #贡献法，用单调递减栈求出在[a,b]区间内nums[i]最大值时的左右边界\n",
    "        n, res = len(nums), 0\n",
    "        left_idx, right_idx = [-1] * n, [n] * n\n",
    "        stk = []\n",
    "        for i in range(n):\n",
    "            while stk and nums[stk[-1]] < nums[i]:\n",
    "                right_idx[stk.pop()] = i\n",
    "            stk.append(i)\n",
    "        stk = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stk and nums[stk[-1]] <= nums[i]:\n",
    "                left_idx[stk.pop()] = i\n",
    "            stk.append(i)\n",
    "        for i in range(n):\n",
    "            if left <= nums[i] <= right:\n",
    "                res += (right_idx[i] - i) * (i - left_idx[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, A, L, R):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :type L: int\n",
    "        :type R: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        left = 0\n",
    "        result = []\n",
    "        tmp = 0\n",
    "        \n",
    "        for i, c in enumerate(A):\n",
    "            if c > R:\n",
    "                # 大于 R 的数，分隔 A 为一个个小区间\n",
    "                tmp = 0\n",
    "                left = i + 1\n",
    "            elif c >= L:\n",
    "                # 在小区间内，从左到右，遇到 L <= c <= R，组合数会增加 i - left + 1\n",
    "                tmp = i - left + 1\n",
    "                result.append(tmp)\n",
    "            else:\n",
    "                # 在小区间内，从左到右，遇到 c < L，组合数会增加之前那么多种\n",
    "                result.append(tmp)\n",
    "        return sum(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        stack = []\n",
    "        l = [-1] * n\n",
    "        r = [n] * n\n",
    "        for i, num in enumerate(nums):\n",
    "            while stack and nums[stack[-1]] < num:\n",
    "                j = stack.pop()\n",
    "                r[j] = i\n",
    "            if stack:\n",
    "                l[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        for i, num in enumerate(nums):\n",
    "            if left <= num <= right:\n",
    "                ans += (i - l[i]) * (r[i] - i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        lastAlp = [0] * len(nums)\n",
    "        smallThanLeft = 0\n",
    "        if left <= nums[0] <= right:\n",
    "            lastAlp[0] = 1\n",
    "        elif nums[0] < left:\n",
    "            smallThanLeft += 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] < left:\n",
    "                smallThanLeft += 1\n",
    "                lastAlp[i] = lastAlp[i - 1]\n",
    "            elif left <= nums[i] <= right:\n",
    "                lastAlp[i] = lastAlp[i - 1] + smallThanLeft + 1\n",
    "                smallThanLeft = 0\n",
    "            else:\n",
    "                smallThanLeft = 0\n",
    "        return sum(lastAlp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        def linearsearch(target, l):\n",
    "            for mid in range(l, len(nums)):\n",
    "                if nums[mid] < target:\n",
    "                    return mid\n",
    "        l = 0\n",
    "        cnt = 0\n",
    "        Dict = {}\n",
    "        sta = deque() # 保存最大值，单调递减栈\n",
    "        for r in range(len(nums)): # [l, r]闭区间\n",
    "            while sta and nums[sta[-1]] < nums[r]:\n",
    "                sta.pop()\n",
    "            sta.append(r)\n",
    "            # 不可行窗口可行化\n",
    "            while l <= r and sta and nums[sta[0]] > right:\n",
    "                l = sta.popleft() + 1\n",
    "            if l <= r and sta and nums[sta[0]] >= left:\n",
    "                # mid = binarysearch(sta, left)\n",
    "                if nums[sta[-1]] >= left:\n",
    "                    Dict[l] = r + 1\n",
    "                    cnt += r - l + 1\n",
    "                else:\n",
    "                    if l not in Dict:\n",
    "                        Dict[l] = linearsearch(left, l)\n",
    "                    cnt += Dict[l] - l\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp =[0 for _ in range(n)]\n",
    "        smaller = 0\n",
    "        for i in range(0, n):\n",
    "            if nums[i] > right:\n",
    "                dp[i] = 0\n",
    "                smaller = 0\n",
    "            elif nums[i] >= left:\n",
    "                dp[i] = smaller + 1\n",
    "                smaller += 1\n",
    "            else:\n",
    "                dp[i] = dp[i-1]\n",
    "                smaller += 1\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        smallerCount = [0 for _ in range(len(nums))]\n",
    "        cnt = 0\n",
    "        smaller = 0\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            if nums[i] <= right and nums[i] >= left:\n",
    "                cnt += 1 + smaller\n",
    "                smaller = 0\n",
    "            elif nums[i] < left:\n",
    "                smaller += 1\n",
    "            else:\n",
    "                cnt = 0\n",
    "                smaller = 0\n",
    "            smallerCount[i] = cnt\n",
    "\n",
    "        return sum(smallerCount)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        i_over=-1\n",
    "        dp=[]\n",
    "        if nums[0]>right:\n",
    "            dp.append(0)\n",
    "            i_over=0\n",
    "        elif nums[0]>=left:\n",
    "            dp.append(1)\n",
    "        else:\n",
    "            dp.append(0)\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]>right:\n",
    "                dp.append(0)\n",
    "                i_over = i\n",
    "            elif nums[i]>=left:\n",
    "                dp.append(i-i_over)\n",
    "            else:\n",
    "                dp.append(dp[i-1])\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        def cal(sub_nums):\n",
    "            record = [0] * len(sub_nums)\n",
    "            if len(sub_nums) == 0:\n",
    "                return 0\n",
    "            record[0] = 1 if left <= sub_nums[0] <= right else 0\n",
    "            for j in range(1, len(sub_nums)):\n",
    "                if left <= sub_nums[j] <= right:\n",
    "                    record[j] = j + 1\n",
    "                else:\n",
    "                    record[j] = record[j - 1]\n",
    "            return sum(record)\n",
    "\n",
    "        i = 0\n",
    "        while nums[i] > right and i < len(nums):\n",
    "            i += 1\n",
    "        last = i\n",
    "        res = 0\n",
    "        for i in range(i, len(nums)):\n",
    "            if nums[i] > right:\n",
    "                res += cal(nums[last:i])\n",
    "                last = i + 1\n",
    "        if nums[-1] <= right:\n",
    "            res += cal(nums[last:i + 1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], a: int, b: int) -> int:\n",
    "        n, ans = len(nums), 0\n",
    "        l, r = [-1] * n, [n] * n\n",
    "        stk = []\n",
    "        for i in range(n):\n",
    "            while stk and nums[stk[-1]] < nums[i]:\n",
    "                r[stk.pop()] = i\n",
    "            if stk:\n",
    "                l[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "\n",
    "        for i in range(n):\n",
    "            if a <= nums[i] <= b:\n",
    "                ans += (i - l[i]) * (r[i] - i)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        dp = [0] * len(nums)\n",
    "        if left <= nums[0] <= right:\n",
    "            dp[0] = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] < left:\n",
    "                dp[i] = dp[i - 1]\n",
    "            elif nums[i] > right:\n",
    "                dp[i] = 0\n",
    "            else:\n",
    "                dp[i] = dp[i - 1] + 1\n",
    "                temp = i - 1\n",
    "                while temp >= 0 and nums[temp] < left:\n",
    "                    dp[i] += 1\n",
    "                    temp -= 1\n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n=len(nums)\n",
    "        ans=[1]*n\n",
    "        ans[0]=1 if nums[0] >= left and nums[0] <= right else 0\n",
    "        f=0 if nums[0]>right else -1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]<left:\n",
    "                ans[i]=0\n",
    "                ans[i]+=ans[i-1]\n",
    "                \n",
    "   \n",
    "            elif nums[i]>right:\n",
    "                ans[i]=0\n",
    "                f=i\n",
    "            else:\n",
    "                \n",
    "                ans[i]=(i-f)\n",
    "                \n",
    "      \n",
    "        for i,j in zip(ans,nums):\n",
    "            print(i,j)     \n",
    "        return sum(ans)                \n",
    "\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        dp = [0]*len(nums)\n",
    "        if left <= nums[0] <= right:\n",
    "            dp[0] = 1\n",
    "        res = dp[0]\n",
    "        max_0 = -1\n",
    "        if nums[0] > right:\n",
    "            max_0 = 0 \n",
    "        for i in range(1,len(dp)):\n",
    "            if nums[i] > right:\n",
    "                max_0 = i \n",
    "                continue \n",
    "            else:\n",
    "                if left <= nums[i] <= right:\n",
    "                    # 只要不碰壁就能一直选\n",
    "                    dp[i] = i - max_0\n",
    "                else:\n",
    "                    dp[i] = dp[i-1]\n",
    "            res += dp[i]\n",
    "        # print(dp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 定义两个数组，分别保存左边的第一个最大值和右边的第一个最大值的索引\n",
    "        # 注意初始化的时候，应该分别保存最左边和最右边两个值\n",
    "        l,r = [0]*n, [0]*n\n",
    "\n",
    "        # 定义单调栈（单调递减）\n",
    "        stk = []\n",
    "        # 注意当有重复元素时，可能会导致重复子数组\n",
    "        # 所有单调栈时，左闭右开或者左开右闭\n",
    "        for idx, num in enumerate(nums):\n",
    "\n",
    "            while stk and num >= nums[stk[-1]]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                l[idx] = stk[-1]\n",
    "            # 可以不用写，在初始化的时候解决就可以了这里写是因为为了逻辑清晰\n",
    "            else:\n",
    "                l[idx] = -1\n",
    "            stk.append(idx)\n",
    "\n",
    "        stk = []\n",
    "        for idx in range(n-1,-1,-1):\n",
    "            num = nums[idx]\n",
    "            # 左边界的时候，是>=,这里选择>, 避免重复\n",
    "            while stk and num > nums[stk[-1]]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                r[idx] = stk[-1]\n",
    "            else:\n",
    "                r[idx] = n\n",
    "            stk.append(idx)\n",
    "        print(l,r)\n",
    "        res = 0\n",
    "        for idx in range(n):\n",
    "            if left <= nums[idx] <= right:\n",
    "                res += (idx-l[idx])*(r[idx]-idx)\n",
    "        return res\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        cnt = 0\n",
    "        dp = len(nums) * [None]\n",
    "        debit=0\n",
    "        for i,num in enumerate(nums):\n",
    "            if i == 0:\n",
    "                if num <= right and num>=left:\n",
    "                    dp[0] = 1\n",
    "                else:\n",
    "                    dp[0]=0\n",
    "                if num < left:\n",
    "                    debit+=1\n",
    "                continue\n",
    "            cnt += dp[i-1]\n",
    "            if num > right:\n",
    "                dp[i] = 0\n",
    "                debit=0\n",
    "            elif num < left:\n",
    "                dp[i] = dp[i-1] \n",
    "                debit += 1\n",
    "            else:\n",
    "                dp[i] = dp[i-1]  + 1\n",
    "                j = i\n",
    "                if nums[j-1] < left:\n",
    "                    print(debit)\n",
    "                    dp[i] += debit\n",
    "                    debit=0\n",
    "                    \n",
    "        print(dp)\n",
    "        return  cnt+dp[-1]\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        cnt = 0\n",
    "        dp = len(nums) * [None]\n",
    "        for i,num in enumerate(nums):\n",
    "            if i == 0:\n",
    "                if num <= right and num>=left:\n",
    "                    dp[0] = 1\n",
    "                else:\n",
    "                    dp[0]=0\n",
    "                continue\n",
    "            if num > right:\n",
    "                dp[i] = 0\n",
    "                cnt = dp[i-1] + cnt\n",
    "            elif num < left:\n",
    "                dp[i] = dp[i-1] \n",
    "            else:\n",
    "                dp[i] = dp[i-1]  + 1\n",
    "                j = i\n",
    "                while nums[j-1] < left and (j-1)>=0:\n",
    "                    dp[i] += 1\n",
    "                    j = j-1\n",
    "                \n",
    "                    \n",
    "        \n",
    "        print(dp)\n",
    "        return  sum(dp)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        res = 0\n",
    "        mono_st = []\n",
    "        mono_st_pos = []\n",
    "\n",
    "        def binSearchRight(arr, start, end, right, res):\n",
    "            if start > end:\n",
    "                return\n",
    "            \n",
    "            mid = (start + end) // 2\n",
    "            if arr[mid] > right:\n",
    "                binSearchRight(arr, mid + 1, end, right, res)\n",
    "            else:\n",
    "                res[0] = mid\n",
    "                binSearchRight(arr, start, mid - 1, right, res)\n",
    "                \n",
    "        \n",
    "        def binSearchLeft(arr, start, end, left, res):\n",
    "            if start > end:\n",
    "                return\n",
    "            \n",
    "            mid = (start + end) // 2\n",
    "            if arr[mid] < left:\n",
    "                binSearchLeft(arr, start, mid - 1, left, res)\n",
    "            else:\n",
    "                res[0] = mid\n",
    "                binSearchLeft(arr, mid + 1, end, left, res)\n",
    "\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            num = nums[i]\n",
    "\n",
    "            while mono_st and mono_st[-1] < num:\n",
    "                mono_st.pop()\n",
    "                mono_st_pos.pop()\n",
    "\n",
    "            mono_st.append(num)\n",
    "            mono_st_pos.append(i)\n",
    "\n",
    "            if num > right:\n",
    "                continue\n",
    "            elif num < left:\n",
    "                y = [-1]\n",
    "                binSearchRight(mono_st, 0, len(mono_st) - 1, right, y)\n",
    "                x = [-1]\n",
    "                binSearchLeft(mono_st, 0, len(mono_st) - 1, left, x)\n",
    "\n",
    "                if x[0] == -1 or y[0] == -1 or x[0] < y[0]:\n",
    "                    continue\n",
    "                \n",
    "                A = mono_st_pos[y[0] - 1] + 1 if y[0] >= 1 else 0\n",
    "                B = mono_st_pos[x[0]]\n",
    "                res += (B - A + 1)\n",
    "            else:\n",
    "                y = [-1]\n",
    "                binSearchRight(mono_st, 0, len(mono_st) - 1, right, y)\n",
    "                B = i\n",
    "                A = mono_st_pos[y[0] - 1] + 1 if y[0] >= 1 else 0\n",
    "                res += (B - A + 1)\n",
    "        \n",
    "        return res\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        cnt = 0\n",
    "        dp = len(nums) * [None]\n",
    "        for i,num in enumerate(nums):\n",
    "            if i == 0:\n",
    "                if num <= right and num>=left:\n",
    "                    dp[0] = 1\n",
    "                else:\n",
    "                    dp[0]=0\n",
    "                continue\n",
    "            if num > right:\n",
    "                dp[i] = 0\n",
    "                cnt = dp[i-1] + cnt\n",
    "            elif num < left:\n",
    "                dp[i] = dp[i-1] \n",
    "            else:\n",
    "                dp[i] = dp[i-1]  + 1\n",
    "                j = i\n",
    "                while nums[j-1] < left and (j-1)>=0:\n",
    "                    dp[i] += 1\n",
    "                    j = j-1\n",
    "                \n",
    "                    \n",
    "        \n",
    "        print(dp)\n",
    "        return  sum(dp)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        ans = 0\n",
    "        stk = []\n",
    "        arr = [inf] + nums + [inf]\n",
    "        for i, x in enumerate(arr):\n",
    "            while stk and x > arr[stk[-1]]:\n",
    "                r = i - stk[-1]\n",
    "                l = stk[-1] - stk[-2]\n",
    "                if left <= arr[stk[-1]] <= right:\n",
    "                    ans += l * r\n",
    "                stk.pop()\n",
    "            stk.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        res = 0\n",
    "        stack = []\n",
    "        nums = [float('inf')] + nums + [float('inf')]\n",
    "        for i, x in enumerate(nums):\n",
    "            while stack and nums[stack[-1]] < x:\n",
    "                idx = stack.pop()\n",
    "                if nums[idx] >= left and nums[idx] <= right:\n",
    "                    peak = stack[-1]\n",
    "                    res += (i-idx) * (idx-peak)\n",
    "            stack.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        p1 = [None] * n\n",
    "        p2 = [None] * n\n",
    "\n",
    "        if left <= nums[n-1] <= right:\n",
    "            p1[n-1] = n-1\n",
    "        if nums[n-1] > right:\n",
    "            p2[n-1] = n-1\n",
    "\n",
    "        for i in range(n-2, -1, -1):\n",
    "            p1[i] = p1[i+1]\n",
    "            p2[i] = p2[i+1]\n",
    "\n",
    "            if left <= nums[i] <= right:\n",
    "                p1[i] = i\n",
    "            if nums[i] > right:\n",
    "                p2[i] = i\n",
    "\n",
    "        print(p1, p2)\n",
    "\n",
    "        tot = 0\n",
    "        for i in range(n):\n",
    "            a, b = p1[i], p2[i]\n",
    "            if a is None:\n",
    "                continue\n",
    "\n",
    "            if b is None:\n",
    "                tot += n - a\n",
    "            else:\n",
    "                if b > a:\n",
    "                    tot += b - a\n",
    "\n",
    "        return tot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "\n",
    "        nums = [float('inf')] + nums + [float('inf')]\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        right_stack = [0] * n\n",
    "        left_stack = [0] * n\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        for i in range(n):\n",
    "            while stack and nums[i] >= nums[stack[-1]]:\n",
    "                idx = stack.pop()\n",
    "                \n",
    "                right_stack[idx] = i\n",
    "                \n",
    "            stack.append(i)\n",
    "            \n",
    "        stack = []\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while stack and nums[i] > nums[stack[-1]]:\n",
    "                idx = stack.pop()\n",
    "                \n",
    "                left_stack[idx] = i\n",
    "                \n",
    "            stack.append(i)\n",
    "            \n",
    "        res = 0\n",
    "        pre_max = -1\n",
    "\n",
    "        for i in range(1,n-1):\n",
    "            \n",
    "            if nums[i] >= left and nums[i] <= right:\n",
    "                res += (right_stack[i]-i) * (i-left_stack[i])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        allsame=True\n",
    "        n=len(nums)\n",
    "        for num in nums:\n",
    "            if not num==nums[0]:\n",
    "                allsame=False\n",
    "        if allsame:\n",
    "            return (n+1)*n//2\n",
    "        rbound=[0 for i in range(n)]\n",
    "        lbound=[0 for i in range(n)]\n",
    "        stack=[]\n",
    "        for i in range(n):\n",
    "            while len(stack)>0 and stack[-1][0]<=nums[i]:\n",
    "                rbound[stack[-1][1]]=i-stack[-1][1]-1\n",
    "                stack=stack[:-1]\n",
    "            stack.append([nums[i],i])\n",
    "        while len(stack)>0:\n",
    "            rbound[stack[-1][1]]=n-stack[-1][1]-1\n",
    "            stack=stack[:-1]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while len(stack)>0 and stack[-1][0]<nums[i]:\n",
    "                lbound[stack[-1][1]]=stack[-1][1]-i-1\n",
    "                stack=stack[:-1]\n",
    "            stack.append([nums[i],i])\n",
    "        while len(stack)>0:\n",
    "            lbound[stack[-1][1]]=stack[-1][1]\n",
    "            stack=stack[:-1]\n",
    "        ans=0\n",
    "        #print(lbound,rbound)\n",
    "        for i in range(n):\n",
    "            if nums[i]>=left and nums[i]<=right:\n",
    "                ans+=(lbound[i]+1)*(rbound[i]+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "\n",
    "        nums = [float('inf')] + nums + [float('inf')]\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        right_stack = [0] * n\n",
    "        left_stack = [0] * n\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        for i in range(n):\n",
    "            while stack and nums[i] >= nums[stack[-1]]:\n",
    "                idx = stack.pop()\n",
    "                \n",
    "                right_stack[idx] = i\n",
    "                \n",
    "            stack.append(i)\n",
    "            \n",
    "        stack = []\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while stack and nums[i] > nums[stack[-1]]:\n",
    "                idx = stack.pop()\n",
    "                \n",
    "                left_stack[idx] = i\n",
    "                \n",
    "            stack.append(i)\n",
    "            \n",
    "        res = 0\n",
    "        pre_max = -1\n",
    "\n",
    "        for i in range(1,n-1):\n",
    "            \n",
    "            if nums[i] >= left and nums[i] <= right:\n",
    "                res += (right_stack[i]-i) * (i-left_stack[i])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left_: int, right_: int) -> int:\n",
    "       # 单调栈\n",
    "        n = len(nums)\n",
    "        # 左边比自己大的最近的位置\n",
    "        left, st = [-1] * n, []\n",
    "        for i, v in enumerate(nums):\n",
    "            while st and nums[st[-1]] < v: st.pop()\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        \n",
    "        # 右边比自己大于等于的最近的位置\n",
    "        right, st = [n] * n, []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while st and nums[st[-1]] <= nums[i]: st.pop()\n",
    "            if st: right[i] = st[-1]\n",
    "            st.append(i)\n",
    "        \n",
    "        # 当前元素作为最大值的区域\n",
    "        print(left)\n",
    "        print(right)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            l, r = i - left[i], right[i] - i\n",
    "            if left_ <= nums[i] <= right_:\n",
    "                print(nums[i], l, r)\n",
    "                ans += l * r\n",
    "        return ans\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        \n",
    "        total = 0\n",
    "        length = len(nums)\n",
    "        left_max_idx = [0 for i in range(length)]\n",
    "\n",
    "        queue = []\n",
    "        for (i, num) in enumerate(nums):\n",
    "            while queue and num >= queue[-1][1]:\n",
    "                prev_i, prev_num = queue.pop()\n",
    "            left_max_idx[i] = queue[-1][0] + 1 if queue else 0\n",
    "            queue.append((i, num))\n",
    "        \n",
    "        queue = []\n",
    "        for (i, num) in enumerate(nums[::-1]):\n",
    "            i = length - 1 - i\n",
    "            while queue and num > queue[-1][1]:\n",
    "                prev_i, prev_num = queue.pop()\n",
    "            if left <= num <= right:\n",
    "                right_max_idx = queue[-1][0] - 1 if queue else length - 1\n",
    "                total += ((i - left_max_idx[i] + 1) * (right_max_idx - i + 1))\n",
    "            queue.append((i, num))\n",
    "        \n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums); l, r = [-1] * n, [n] * n\n",
    "        ms = []\n",
    "        for i in range(n):\n",
    "            while ms and nums[ms[-1]] <= nums[i]:\n",
    "                r[ms.pop()] = i\n",
    "            ms.append(i)\n",
    "        ms = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while ms and nums[ms[-1]] < nums[i]:\n",
    "                l[ms.pop()] = i\n",
    "            ms.append(i)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if left <= nums[i] <= right:\n",
    "                x = (r[i] - i) * (i - l[i])\n",
    "                ans += x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        descs = []\n",
    "        lrange = []\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            while descs and nums[descs[-1]] <= nums[i]: #相等的向左延伸\n",
    "                descs.pop()\n",
    "            if descs:\n",
    "                lrange.append(descs[-1])\n",
    "            else:\n",
    "                lrange.append(-1)\n",
    "            descs.append(i)\n",
    "\n",
    "        descs = []\n",
    "        rrange = []\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            while descs and nums[descs[-1]] < nums[i]: #相等的不向右延伸\n",
    "                descs.pop()\n",
    "            if descs:\n",
    "                rrange.append(descs[-1])\n",
    "            else:\n",
    "                rrange.append(len(nums))\n",
    "            descs.append(i)\n",
    "        rrange = rrange[::-1]\n",
    "\n",
    "        # print(lrange, rrange)\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < left or nums[i] > right:\n",
    "                continue\n",
    "            # print(i, nums[i], rrange[i], lrange[i], rrange[i] - lrange[i] - 1)\n",
    "            ans += (rrange[i] - i) * (i - lrange[i])\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        #求max不超过threshold的子数组个数\n",
    "        def sliding_window(nums, threshold):\n",
    "            heap = []\n",
    "            cnt = defaultdict(int)\n",
    "            res = 0\n",
    "            l, r = 0, 0\n",
    "            while r < len(nums):\n",
    "                cnt[nums[r]] += 1\n",
    "                heapq.heappush(heap, -nums[r])\n",
    "                #堆+字典记数，维护区间内的序和最大值\n",
    "                while l < r and ( -heap[0] > threshold):\n",
    "                    cnt[nums[l]] -= 1\n",
    "                    while heap and cnt[-heap[0]] <= 0:\n",
    "                        heapq.heappop(heap)\n",
    "                    l += 1\n",
    "                if heap and (-heap[0] <= threshold):\n",
    "                    #print(nums[l:r+1], r-l+1)\n",
    "                    res += r-l+1\n",
    "                r += 1\n",
    "            return res\n",
    "        #max在[left,right]区间 = max最大为right的 - max最大为left-1的\n",
    "        return sliding_window(nums, right) - sliding_window(nums, left-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        # >right 一定不可以选, <left当存在一个 [left, right] 的数就可以选 ,  [left, right] 任意选\n",
    "        # 枚举每个数作为子数组的最大值, 尽可能向左向右扩展, 使用单调栈预处理数组, 以O(1)时间获取左右第一个大于该数的索引,\n",
    "        # 左右两侧根据乘法原理计数\n",
    "        # l,r两个数组一个严格, 一个不严格可以避免重复计数问题 同 https://leetcode.cn/problems/sum-of-subarray-minimums/\n",
    "        st = []\n",
    "        n = len(nums)\n",
    "        l = [-1] * n\n",
    "        r = [n] * n\n",
    "        for i, num in enumerate(nums):\n",
    "            while st and num > nums[st[-1]]:\n",
    "                r[st.pop()] = i\n",
    "            if st: \n",
    "                l[i] = st[-1]\n",
    "            st.append(i)\n",
    "        res = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if left <= num <= right: # 枚举每个数作为子数组的最大值, 尽可能向左向右扩展, 最大值必须在[left, right]内\n",
    "                res += (r[i] - i) * (i - l[i]) # [i, r[i]) 以及 (l[i] ,i]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        S = [0] * (len(nums)+1)\n",
    "        pos = [0] * (len(nums)+1)\n",
    "        count = [0] * (len(nums)+1)\n",
    "        index = -1\n",
    "        S[index] = 1000000001\n",
    "        pos[index] = index\n",
    "        for i in range(len(nums)):\n",
    "            item = nums[i]\n",
    "            while S[index] < item:\n",
    "                index -= 1\n",
    "            temp = pos[index]\n",
    "            index += 1\n",
    "            S[index] = item\n",
    "            pos[index] = i\n",
    "\n",
    "            if left <= item <= right:\n",
    "                count[i] = count[temp] + i - temp\n",
    "            elif item < left:\n",
    "                count[i] = count[i-1]\n",
    "        return sum(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        l = [-1]*n\n",
    "        r = [n]*n\n",
    "        mono_stack = []\n",
    "        for i in range(n):\n",
    "            while mono_stack and nums[i] > nums[mono_stack[-1]]:\n",
    "                mono_stack.pop()\n",
    "            if mono_stack: l[i] = mono_stack[-1]\n",
    "            mono_stack.append(i)\n",
    "\n",
    "        mono_stack = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while mono_stack and nums[i] >= nums[mono_stack[-1]]:\n",
    "                mono_stack.pop()\n",
    "            if mono_stack: r[i] = mono_stack[-1]\n",
    "            mono_stack.append(i)\n",
    "        return sum([(i-l[i])*(r[i]-i) for i in range(n) if left<=nums[i]<=right])\n",
    "        \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        l, r = [0] * n, [0] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and nums[i] > nums[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                l[i] = i - stack[-1]\n",
    "            else:\n",
    "                l[i] = i + 1\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and nums[i] >= nums[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                r[i] = stack[-1] - i\n",
    "            else:\n",
    "                r[i] = n - i\n",
    "            stack.append(i)\n",
    "            \n",
    "        ans = 0\n",
    "        # print(l, r)\n",
    "        for i in range(n):\n",
    "            if left <= nums[i] <= right:\n",
    "                ans += l[i] * r[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        L = [-1] * n\n",
    "        R = [n] * n\n",
    "        res = 0\n",
    "\n",
    "        stack = []\n",
    "        # decreasing \n",
    "        # idx\n",
    "\n",
    "\n",
    "        for i, val in enumerate(nums):\n",
    "            while stack and val > nums[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                L[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        stack = []\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            val = nums[i]\n",
    "            while stack and val >= nums[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                R[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        for i, (x, l, r) in enumerate(zip(nums, L, R)):\n",
    "            if left <= x <= right:\n",
    "                res += (i - l) * (r - i)\n",
    "        return res\n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        lmin = [-1] * n\n",
    "        rmin = [n] * n\n",
    "\n",
    "        stk = []\n",
    "        for i in range(n):\n",
    "            while stk and nums[stk[-1]] < nums[i]:\n",
    "                rmin[stk.pop()] = i \n",
    "            stk.append(i) \n",
    "        \n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stk and nums[stk[-1]] <= nums[i]:\n",
    "                lmin[stk.pop()] = i \n",
    "            stk.append(i) \n",
    "\n",
    "        res = 0 \n",
    "        for i in range(n):\n",
    "            if nums[i] >= left and nums[i] <= right:\n",
    "                res += (i - lmin[i]) * (rmin[i] - i)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "\n",
    "        '''\n",
    "        对于某个在[left, right]的数x, 需要x作为子数组的最大值\n",
    "        因此可以用单调栈来寻找x右侧比x大的数\n",
    "\n",
    "        为了方便, 可以假设-1的位置上有个inf\n",
    "        '''\n",
    "        \n",
    "        st = [-1, 0] # 单调递减的栈\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            while len(st) >= 2 and nums[i] > nums[st[-1]]:\n",
    "                if left <= nums[st[-1]] <= right:\n",
    "                    # st[-2]是左侧最近的比st[-1]大的数, i是右侧\n",
    "                    ans += (i-st[-1]) * (st[-1] - st[-2]) # 将做右侧可以选择的区间进行组合\n",
    "                st.pop()\n",
    "            st.append(i)\n",
    "\n",
    "        # 对于某些x, 他的右边没有比他大的数, 可以假设在n的位置上有个inf\n",
    "        while len(st) >= 2:\n",
    "            if left <= nums[st[-1]] <= right:\n",
    "                ans += (n-st[-1]) * (st[-1] - st[-2])\n",
    "            st.pop()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        # [] * [] * * [] .... \n",
    "        # 有一些max会超出right] 显然tm会把array分成几段，那些max不能在任何subarray中\n",
    "        # 但又要求 subarray 的max要大于 left，例如\n",
    "        # 113 [2,4] 只有包含3的subarray满足条件 11 单独不行\n",
    "        # 所以我们考虑 subarray\n",
    "        # [ & & ] * [ & ] * []\n",
    "        # & 为正好处于[left,right]的元素，* 为超界\n",
    "        # 只考虑 & 所在的subarray的全部组合\n",
    "        \n",
    "        # 如果考虑&对应的所有subarray\n",
    "        # 不如考虑以 & 为 max 的 subarray 的全部数量 -- 贡献法\n",
    "        # 这也就绕开了 * \n",
    "        # 快速计算 需要知道 & 左侧右侧最近的一个他大的人 - 单调栈\n",
    "        n = len(nums)\n",
    "        leftG = [-1]*n \n",
    "        rightG = [n]*n\n",
    "        stack = []\n",
    "        for i, x in enumerate(nums):\n",
    "            while len(stack) > 0 and nums[stack[-1]] <= x: # 对于x右侧的人，会只看到x\n",
    "                # 对于弹出去的人，x是第一个让他们弹出去的人，即为rightMax\n",
    "                d = stack.pop(-1)\n",
    "                rightG[d] = i\n",
    "            # 对于x他的左边第一个比他大的人 就是栈下面一个\n",
    "            leftG[i] = stack[-1] if len(stack)>0 else -1\n",
    "            stack.append(i)\n",
    "        # 结束后栈非空 他们的rightG都是n\n",
    "        for k in stack:\n",
    "            rightG[k] = n\n",
    "\n",
    "        res = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if left <= x and x <= right:\n",
    "                # 以x为max的最长subarray\n",
    "                # [leftG[x]+1, x, rightG[x]-1] \n",
    "                res += (i-leftG[i])*(rightG[i]-i)\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n=len(nums)\n",
    "        l=[-1]*n\n",
    "        r=[n]*n\n",
    "        st=[]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while st and nums[i]>nums[st[-1]]:\n",
    "                l[st.pop()]=i\n",
    "            st.append(i)\n",
    "        st=[]\n",
    "        for i in range(n):\n",
    "            while st and nums[i]>=nums[st[-1]]:\n",
    "                r[st.pop()]=i\n",
    "            st.append(i)\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            if left<=nums[i]<=right:\n",
    "                res+=(i-l[i])*(r[i]-i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "\n",
    "        nums = [float('inf')] + nums + [float('inf')]\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            while stack and nums[i] > nums[stack[-1]]:\n",
    "                idx = stack.pop()\n",
    "                \n",
    "                if nums[idx] >= left and nums[idx] <= right:\n",
    "                    cur1 = idx - stack[-1]\n",
    "                    cur2 = i - idx\n",
    "                    \n",
    "                    res += cur1 * cur2\n",
    "                    \n",
    "            stack.append(i)\n",
    "\n",
    "        return res\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, arr: List[int], l1: int, r1: int) -> int:\n",
    "        n = len(arr)\n",
    "        left = [-1] * n\n",
    "        # find bigger val than cur val\n",
    "        right = [n] * n\n",
    "        # find bigger or equal than cur val\n",
    "        stack = []\n",
    "        for i, num in enumerate(arr):\n",
    "            while stack and num >= arr[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "            \n",
    "        \n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and arr[i] > arr[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        res = 0\n",
    "        for i, (x, l, r) in enumerate(zip(arr, left, right)):\n",
    "            if l1 <= x <= r1:\n",
    "                res += (i - l) * (r - i) \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        l = [-1 for _ in range(n)]\n",
    "        r = [n for _ in range(n)]\n",
    "\n",
    "        stk = []\n",
    "        for i, num in enumerate(nums):\n",
    "            while stk and nums[stk[-1]] < num:\n",
    "                r[stk.pop()] = i\n",
    "            stk.append(i)\n",
    "\n",
    "        stk = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            num = nums[i]\n",
    "            while stk and nums[stk[-1]] <= num:\n",
    "                l[stk.pop()] = i\n",
    "            stk.append(i)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] >= left and nums[i] <= right:\n",
    "                res += (i - l[i]) * (r[i] - i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        l, r = [n] * n, [-1] * n\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            while q and nums[q[-1]] <= nums[i]:\n",
    "                l[q.pop()] = i\n",
    "            q.append(i)\n",
    "        q = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while q and nums[q[-1]] < nums[i]:\n",
    "                r[q.pop()] = i\n",
    "            q.append(i)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if left <= nums[i] <= right:\n",
    "                res += (l[i] - i) * (i - r[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        # if cur_num < left || cur_num > right\n",
    "        n, ans = len(nums), 0\n",
    "        L, R = [0] * n, [0] * n\n",
    "        s1, s2 = [], []\n",
    "\n",
    "        for i in range(n):\n",
    "            while s1 and nums[s1[-1]] <= nums[i]:\n",
    "                s1.pop() \n",
    "            L[i] = s1[-1] + 1 if s1 else 0\n",
    "            s1.append(i)\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while s2 and nums[s2[-1]] < nums[i]:\n",
    "                s2.pop()\n",
    "            R[i] = s2[-1] - 1 if s2 else n - 1\n",
    "            s2.append(i)\n",
    "    \n",
    "        for i in range(n):\n",
    "            if nums[i] < left or nums[i] > right:\n",
    "                continue\n",
    "            else:\n",
    "                # 当前数字作为最大值落在 [left, right] 范围内\n",
    "\n",
    "                # 左侧数字不能大于当前(小,等于可以)\n",
    "                ans += (i - L[i] + 1) * (R[i] - i + 1)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        left_bounds = [-1] * n\n",
    "        right_bounds = [n] * n\n",
    "        mono_stack = []\n",
    "        for i in range(n):\n",
    "            while mono_stack and nums[mono_stack[-1]] <= nums[i]:\n",
    "                right_bounds[mono_stack.pop(-1)] = i\n",
    "            mono_stack.append(i)\n",
    "        \n",
    "        mono_stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while mono_stack and nums[mono_stack[-1]] < nums[i]:\n",
    "                left_bounds[mono_stack.pop(-1)] = i\n",
    "            mono_stack.append(i)\n",
    "        #print('left_bounds:', str(left_bounds))\n",
    "        #print('right_bounds:', str(right_bounds))\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if left <= nums[i] <= right:\n",
    "                ans += (i - left_bounds[i]) * (right_bounds[i] - i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        l = [-1]*n\n",
    "        r = [n]*n\n",
    "        mystc = [0]\n",
    "        for ii in range(1,n):\n",
    "            while mystc and nums[ii]>=nums[mystc[-1]]:\n",
    "                mystc.pop()\n",
    "            if mystc:\n",
    "                l[ii] = mystc[-1]\n",
    "            mystc.append(ii)\n",
    "        mystc = [n-1]\n",
    "        for ii in range(n-2,-1,-1):\n",
    "            while mystc and nums[ii]>nums[mystc[-1]]:\n",
    "                mystc.pop()\n",
    "            if mystc:\n",
    "                r[ii] = mystc[-1]\n",
    "            mystc.append(ii)\n",
    "        res = 0\n",
    "        for ii in range(n):\n",
    "            if nums[ii]>=left and nums[ii]<=right:\n",
    "                li = l[ii]\n",
    "                ri = r[ii]\n",
    "                ll = ii-li\n",
    "                rl = ri-ii\n",
    "                res+=ll*rl\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n=len(nums)\n",
    "        l=[-1]*n\n",
    "        r=[n]*n  \n",
    "        d=[]\n",
    "        for i in range(n):\n",
    "            while d and nums[d[-1]]<nums[i]:\n",
    "                r[d.pop()]=i\n",
    "            d.append(i)\n",
    "        d.clear()\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while d and nums[d[-1]]<=nums[i]:\n",
    "                l[d.pop()]=i\n",
    "            d.append(i)\n",
    "        ans=0\n",
    "        for i,x in enumerate(nums):\n",
    "            if x<left or x>right:\n",
    "                continue\n",
    "            ans+=(i-l[i])*(r[i]-i)\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        def f(nums, right, op):\n",
    "            n = len(nums)\n",
    "            record = []\n",
    "            for i in range(n):\n",
    "                if op == 1:\n",
    "                    if nums[i] > right:\n",
    "                        record.append(i)\n",
    "                if op == 0:\n",
    "                    if nums[i] >= right:\n",
    "                        record.append(i)\n",
    "            res = 0\n",
    "            record = [-1] + record + [n]\n",
    "            for i in range(0, len(record) - 1):\n",
    "                res += round((record[i + 1] - record[i] - 1) * (record[i + 1] - record[i])/2)\n",
    "            return res\n",
    "        return f(nums, right, 1) - f(nums, left, 0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        n = len(nums)\n",
    "        rb = [n] * n    # rb[i] = j 表示 nums[j] 是 nums[i] 右侧第一个比 nums[i] 大的数\n",
    "        stack = []      # stack 维持非严格降序索引\n",
    "        for j in range(n):\n",
    "            while stack and nums[stack[-1]] < nums[j]:\n",
    "                rb[stack.pop()] = j\n",
    "            stack.append(j)\n",
    "        lb = [-1] * n\n",
    "        stack = []\n",
    "        for j in range(n-1, -1, -1):\n",
    "            while stack and nums[stack[-1]] <= nums[j]:\n",
    "                lb[stack.pop()] = j\n",
    "            stack.append(j)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if left <= nums[i] <= right:\n",
    "                res += (i - lb[i]) * (rb[i] - i)\n",
    "        return res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], l: int, r: int) -> int:\n",
    "        '''\n",
    "        好难好难\n",
    "        子问题\n",
    "        看错题目了。。。\n",
    "\n",
    "        '''\n",
    "        st=[-1]\n",
    "        n=len(nums)\n",
    "        right=[n]*n\n",
    "        left=[-1]*n\n",
    "        for i,x in enumerate(nums):\n",
    "            while len(st)>1 and nums[st[-1]]<x:\n",
    "                y=st.pop()\n",
    "                right[y]=i\n",
    "            left[i]=st[-1] \n",
    "            st.append(i)\n",
    "        ans=0\n",
    "        for i,x in enumerate(nums):\n",
    "            if l<=x<=r :ans+=(right[i]-i)*(i-left[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            tot = [0] * (m+1)\n",
    "            for k in range(i, n):\n",
    "                cnt = Counter([0])\n",
    "                prv = 0\n",
    "                for j in range(m):\n",
    "                    prv += matrix[k][j]\n",
    "                    tot[j+1] += prv\n",
    "                    ans += cnt[tot[j+1] - target]\n",
    "                    cnt[tot[j+1]] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def subarraySum(nums, k):\n",
    "            cnter = defaultdict(int)\n",
    "            cnter[0] = 1\n",
    "            ans = 0\n",
    "            prefix_sum = 0\n",
    "            for num in nums:\n",
    "                prefix_sum += num\n",
    "                ans += cnter[prefix_sum - k]\n",
    "                cnter[prefix_sum] += 1\n",
    "            return ans\n",
    "\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        res = 0\n",
    "\n",
    "        # 枚举上边界\n",
    "        for i in range(m):\n",
    "            col_sum = [0] * n\n",
    "\n",
    "            # 枚举下边界\n",
    "            for j in range(i, m):\n",
    "                for col in range(n):\n",
    "                    col_sum[col] += matrix[j][col]\n",
    "                res += subarraySum(col_sum, target)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        n = len(matrix)\n",
    "        m = len(matrix[0])\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            s = [0] * m\n",
    "            for j in range(i, n):\n",
    "                for k in range(m):\n",
    "                    s[k] += matrix[j][k]\n",
    "                mp = defaultdict(int)\n",
    "                mp[0] = 1\n",
    "                sum = 0\n",
    "                for x in s:\n",
    "                    sum += x\n",
    "                    ans += mp[sum - target]\n",
    "                    mp[sum] += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def subarraySum(nums: List[int], k: int) -> int:\n",
    "            mp = Counter([0])\n",
    "            count = pre = 0\n",
    "            for x in nums:\n",
    "                pre += x\n",
    "                if pre - k in mp:\n",
    "                    count += mp[pre - k]\n",
    "                mp[pre] += 1\n",
    "            return count\n",
    "        \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        # 枚举上边界\n",
    "        for i in range(m):\n",
    "            total = [0] * n\n",
    "            # 枚举下边界\n",
    "            for j in range(i, m):\n",
    "                for c in range(n):\n",
    "                    # 更新每列的元素和\n",
    "                    total[c] += matrix[j][c]\n",
    "                ans += subarraySum(total, target)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix, target):\n",
    "        res = 0\n",
    "        nrow, ncol = len(matrix), len(matrix[0])\n",
    "        nsum = [0]*ncol\n",
    "        for i in range(nrow):\n",
    "            for j in range(i, nrow):\n",
    "                for k in range(ncol):\n",
    "                    nsum[k] += matrix[j][k]\n",
    "                for k in range(ncol):\n",
    "                    tmp = 0\n",
    "                    for l in range(k, ncol):\n",
    "                        tmp += nsum[l]\n",
    "                        if tmp == target:\n",
    "                            res += 1\n",
    "            nsum = [0]*ncol\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def cal(self, arr, target):\n",
    "        res = 0\n",
    "        d = {}\n",
    "        \n",
    "        preS = [0]*len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            if i == 0:\n",
    "                preS[i] = arr[i]\n",
    "            else:\n",
    "                preS[i] = preS[i-1] + arr[i]\n",
    "        \n",
    "        for i in range(len(preS)):\n",
    "            if preS[i] == target:\n",
    "                res += 1\n",
    "            res += d.get(preS[i] - target, 0)\n",
    "            d[preS[i]] = d.get(preS[i], 0) + 1\n",
    "        return res\n",
    "\n",
    "    def numSubmatrixSumTarget(self, matrix, target):\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        res = 0\n",
    "        \n",
    "        for i in range(m):\n",
    "            # 上边界i\n",
    "            preSum = [0] * n\n",
    "            for j in range(i, m):\n",
    "                # 下边界j\n",
    "                # update preSum\n",
    "                for k in range(n):\n",
    "                    preSum[k] += matrix[j][k]\n",
    "                res += self.cal(preSum, target)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        for top in range(m):\n",
    "            rowPrefix = [0] * n\n",
    "            for bottom in range(top, m):\n",
    "                colPrefix = 0\n",
    "                colprefix_dict = {0:1}\n",
    "                for left in range(n):\n",
    "                    rowPrefix[left] += matrix[bottom][left]\n",
    "                    colPrefix += rowPrefix[left]\n",
    "                    if colPrefix - target in colprefix_dict:\n",
    "                        ans += colprefix_dict[colPrefix - target]\n",
    "                    if colPrefix in colprefix_dict:\n",
    "                        colprefix_dict[colPrefix] += 1\n",
    "                    else:\n",
    "                        colprefix_dict[colPrefix] = 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        ans = 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for i in range(m):\n",
    "            row = [0] * n\n",
    "            for j in range(i, m):\n",
    "                for k in range(n):\n",
    "                    row[k] += matrix[j][k]\n",
    "                s = 0\n",
    "                last = defaultdict(int) \n",
    "                last[0] = 1\n",
    "                for x in row:\n",
    "                    s += x\n",
    "                    ans += last[s - target]\n",
    "                    last[s] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        \n",
    "        res = 0\n",
    "        r, c = len(matrix), len(matrix[0])\n",
    "\n",
    "\n",
    "        for i in range(r):\n",
    "            tmp = [0] * c \n",
    "            for j in range(i, r):\n",
    "                mp = collections.defaultdict(int)\n",
    "                mp[0] = 1\n",
    "                presum = 0\n",
    "                for k in range(c):\n",
    "                    tmp[k] += matrix[j][k]\n",
    "                    presum += tmp[k]\n",
    "                    res += mp.get(presum - target, 0)\n",
    "                    mp[presum] += 1\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        if m > n:\n",
    "            matrix = list(zip(*matrix))\n",
    "            m, n = n, m\n",
    "        ans = 0\n",
    "        mp = defaultdict(int)\n",
    "        for t in range(m):\n",
    "            rowsum = [0] * n\n",
    "            for b in range(t, m):\n",
    "                mp.clear()\n",
    "                mp[0] = 1\n",
    "                colsum = 0\n",
    "                for c in range(n):\n",
    "                    rowsum[c] += matrix[b][c]\n",
    "                    colsum += rowsum[c]\n",
    "                    ans += mp.get(colsum - target, 0)\n",
    "                    mp[colsum] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m ,n = len(matrix), len(matrix[0])\n",
    "        for i in range(m):\n",
    "            for j in range(1,n):\n",
    "                matrix[i][j] += matrix[i][j-1]\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                c = collections.defaultdict(int)\n",
    "                pre = 0\n",
    "                c[0]=1\n",
    "                for k in range(m):\n",
    "                    pre+= matrix[k][j]-(0 if i==0 else matrix[k][i-1])\n",
    "                    ans+=c[pre-target]\n",
    "                    c[pre]+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        res = 0\n",
    "        for left in range(m):\n",
    "            sumnum = [0]*n \n",
    "            for right in range(left, m):\n",
    "                prexi = [0]*(n+1)\n",
    "                for i in range(n):\n",
    "                    sumnum[i] += matrix[right][i]\n",
    "                dic = Counter([0])\n",
    "                pre = 0\n",
    "                for e in sumnum:\n",
    "                    pre += e\n",
    "                    if pre - target in dic:\n",
    "                        res += dic[pre-target]\n",
    "                    dic[pre] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            col_sum = [0] * n\n",
    "            for j in range(i, m):\n",
    "                seen = collections.defaultdict(int)\n",
    "                seen[0] += 1\n",
    "                area_sum = [0]\n",
    "                for k in range(n):\n",
    "                    col_sum[k] += matrix[j][k] \n",
    "                    area_sum.append(area_sum[-1] + col_sum[k])\n",
    "                    ans += seen[area_sum[-1] - target] \n",
    "                    seen[area_sum[-1]] += 1\n",
    "        return ans  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def subarraySum(nums: List[int], k: int) -> int:\n",
    "            cnt = Counter([0])\n",
    "            \n",
    "            cur = 0\n",
    "            ans = 0\n",
    "            for num in nums:\n",
    "                cur += num\n",
    "                if cnt[cur-k]>0:\n",
    "                    ans+=cnt[cur-k]\n",
    "                cnt[cur]+=1\n",
    "            return ans\n",
    "        m,n = len(matrix), len(matrix[0])\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            t = [0]*n\n",
    "            for j in range(i,m):\n",
    "                \n",
    "                for k in range(n):\n",
    "                    t[k]+=matrix[j][k]\n",
    "                res += subarraySum(t,target)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "\n",
    "        def cal(col_sum):\n",
    "            cnt = defaultdict(int)\n",
    "            ret = 0\n",
    "            pre_sum = list(accumulate(col_sum, initial = 0))\n",
    "            for x in pre_sum:\n",
    "                ret += cnt[x - target]\n",
    "                cnt[x] += 1\n",
    "            return ret\n",
    "\n",
    "        for i in range(n):\n",
    "            col_sum = [0] * m\n",
    "            for j in range(i, n):\n",
    "                for k in range(m):\n",
    "                    col_sum[k] += matrix[j][k]\n",
    "                ans += cal(col_sum)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def subarraySum(nums: List[int], k: int) -> int:\n",
    "            dct = Counter([0])\n",
    "            cnt, pre = 0, 0\n",
    "            for num in nums:\n",
    "                pre += num\n",
    "                if pre - k in dct:\n",
    "                    cnt += dct[pre - k]\n",
    "                dct[pre] += 1\n",
    "            return cnt\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            total = [0] * n\n",
    "            for j in range(i, m):\n",
    "                for c in range(n):\n",
    "                    total[c] += matrix[j][c]\n",
    "                ans += subarraySum(total, target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "\n",
    "        res = 0\n",
    "        for low in range(n):\n",
    "            sums = [0] * m\n",
    "            for high in range(low, n):\n",
    "                dict = {0 : 1}\n",
    "                tot  = 0\n",
    "                for r in range(m):\n",
    "                    sums[r] += matrix[high][r]\n",
    "                    tot += sums[r]\n",
    "                    if (cur := tot - target) in dict:\n",
    "                        res += dict[cur]\n",
    "                        #dict[cur] += 1\n",
    "                    if tot not in dict:\n",
    "                        dict[tot] = 1\n",
    "                    else:\n",
    "                        dict[tot] += 1\n",
    "                #print(dict)\n",
    "        \n",
    "        return res\n",
    "                    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        Row, Col = len(matrix), len(matrix[0])\n",
    "        res = 0\n",
    "        for L in range(Col):        #L为左边界\n",
    "            row_sum = [0 for _ in range(Row)]   #L为左边界R为右边界，各行的和\n",
    "            for R in range(L, Col):\n",
    "                for r in range(Row):\n",
    "                    row_sum[r] += matrix[r][R]\n",
    "                \n",
    "                pre_sum_cnt_dict = collections.defaultdict(int)\n",
    "                pre_sum_cnt_dict[0] = 1  # 初始时，累加和为0的情况为1\n",
    "                pre_sum = 0\n",
    "                for row_sum_val in row_sum:\n",
    "                    pre_sum += row_sum_val\n",
    "                    if pre_sum - target in pre_sum_cnt_dict:\n",
    "                        res += pre_sum_cnt_dict[pre_sum - target]\n",
    "                    pre_sum_cnt_dict[pre_sum] += 1\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def subarraySum(nums: List[int], k: int) -> int:\n",
    "            mp = Counter([0])\n",
    "            count = pre = 0\n",
    "            for x in nums:\n",
    "                pre += x\n",
    "                if pre - k in mp:\n",
    "                    count += mp[pre - k]\n",
    "                mp[pre] += 1\n",
    "            return count\n",
    "        \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        # 枚举上边界\n",
    "        for i in range(m):\n",
    "            total = [0] * n\n",
    "            # 枚举下边界\n",
    "            for j in range(i, m):\n",
    "                for c in range(n):\n",
    "                    # 更新每列的元素和\n",
    "                    total[c] += matrix[j][c]\n",
    "                ans += subarraySum(total, target)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        if m > n:\n",
    "            matrix = list(zip(*matrix))\n",
    "            m, n = n, m\n",
    "        ans = 0\n",
    "        for t in range(m):\n",
    "            rowsum = [0] * n\n",
    "            for b in range(t, m):\n",
    "                mp = defaultdict(int)\n",
    "                mp[0] = 1\n",
    "                colsum = 0\n",
    "                for c in range(n):\n",
    "                    rowsum[c] += matrix[b][c]\n",
    "                    colsum += rowsum[c]\n",
    "                    ans += mp.get(colsum - target, 0)\n",
    "                    mp[colsum] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def subarraySum(nums, k):\n",
    "            mp = Counter([0])\n",
    "            count = 0\n",
    "            pre = 0\n",
    "            for x in nums:\n",
    "                pre += x\n",
    "                if pre - k in mp:\n",
    "                    count += mp[pre - k]\n",
    "                mp[pre] += 1\n",
    "            return count\n",
    "        \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            total = [0] * n\n",
    "            for j in range(i, m):\n",
    "                for c in range(n):\n",
    "                    total[c] += matrix[j][c]\n",
    "                ans += subarraySum(total, target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "\n",
    "        # 二维前缀和\n",
    "        m , n = len(matrix),len(matrix[0])\n",
    "        s = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                s[i][j] = s[i-1][j]+s[i][j-1]-s[i-1][j-1] + matrix[i-1][j-1]\n",
    "        \n",
    "        res = 0\n",
    "\n",
    "        for top in range(m+1):\n",
    "            for bottom in range(top+1,m+1):\n",
    "                section_presum = defaultdict(int)\n",
    "                section_presum[0] = 1\n",
    "                for col in range(1, n + 1):\n",
    "                    # 一维前缀\n",
    "                    prefix = s[bottom][col] - s[top][col]\n",
    "                    res += section_presum[prefix - target]\n",
    "                    section_presum[prefix] += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def sumarraySum(nums, k):\n",
    "            mp = collections.Counter([0])\n",
    "            count = pre = 0\n",
    "            for x in nums:\n",
    "                pre += x\n",
    "                if pre - k in mp:\n",
    "                    count += mp[pre - k]\n",
    "                mp[pre] += 1\n",
    "            return count\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        # 枚举上边界\n",
    "        for i in range(m):\n",
    "            total = [0] * n \n",
    "            # 枚举下边界\n",
    "            for j in range(i, m):\n",
    "                # 列向右逐渐移动\n",
    "                for c in range(n):\n",
    "                    # 更新每列的元素和\n",
    "                    total[c] += matrix[j][c]\n",
    "                ans += sumarraySum(total, target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, mx: List[List[int]], t: int) -> int:\n",
    "        m,n=len(mx),len(mx[0])\n",
    "        tmp=[[0]*(n+1) for i in range(m+1)]\n",
    "        res=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                tmp[i+1][j+1]=tmp[i][j+1]+tmp[i+1][j]+mx[i][j]-tmp[i][j]\n",
    "        for i in range(m):\n",
    "            for ii in range(i+1,m+1):\n",
    "                temp = [tmp[ii][j]-tmp[i][j] for j in range(n+1)]\n",
    "                for j in range(n):\n",
    "                    for jj in range(j+1,n+1):\n",
    "                        if temp[jj]-temp[j]==t:\n",
    "                            res+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def subarraySum(nums: List[int], k: int) -> int:\n",
    "            mp = Counter([0])\n",
    "            count = pre = 0\n",
    "            for x in nums:\n",
    "                pre += x\n",
    "                if pre - k in mp:\n",
    "                    count += mp[pre - k]\n",
    "                mp[pre] += 1\n",
    "            return count\n",
    "        \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        # 枚举上边界\n",
    "        for i in range(m):\n",
    "            total = [0] * n\n",
    "            # 枚举下边界\n",
    "            for j in range(i, m):\n",
    "                for c in range(n):\n",
    "                    # 更新每列的元素和\n",
    "                    total[c] += matrix[j][c]\n",
    "                ans += subarraySum(total, target)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        pref_sum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                pref_sum[i][j] = pref_sum[i-1][j] + pref_sum[i][j-1] - pref_sum[i-1][j-1] + matrix[i-1][j-1]\n",
    "        \n",
    "        res = 0\n",
    "        for top in range(1, m + 1):\n",
    "            for bottom in range(top, m + 1):\n",
    "                area_freq = {0:1}\n",
    "                for r in range(1, n + 1):\n",
    "                    cur_area = pref_sum[bottom][r] - pref_sum[top-1][r]\n",
    "                    res += area_freq.get(cur_area - target, 0)\n",
    "                    area_freq[cur_area] = area_freq.get(cur_area, 0) + 1          \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for row in matrix:\n",
    "            for i in range(n - 1):\n",
    "                row[i + 1] += row[i]\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                c = collections.defaultdict(int)\n",
    "                cur, c[0] = 0, 1\n",
    "                for k in range(m):\n",
    "                    cur += matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0)\n",
    "                    res += c[cur - target]\n",
    "                    c[cur] += 1\n",
    "        return res    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def cal(self, arr, target):\n",
    "        n = len(arr)\n",
    "        d = {}\n",
    "        res = 0\n",
    "        left = [0]*n\n",
    "        left[0] = arr[0]\n",
    "        for i in range(1, n):\n",
    "            left[i] = left[i-1] + arr[i]\n",
    "\n",
    "        for i in range(n):\n",
    "            if left[i] == target:\n",
    "                res += 1\n",
    "            res += d.get(left[i] - target, 0)\n",
    "            d[left[i]] = d.get(left[i], 0) + 1\n",
    "\n",
    "        return res\n",
    "\n",
    "    def numSubmatrixSumTarget(self, matrix, target):\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        res = 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for i in range(m):\n",
    "            preSum = [0]*n\n",
    "            for j in range(i, m):\n",
    "                # update preSum\n",
    "                for k in range(n):\n",
    "                    preSum[k] += matrix[j][k]\n",
    "                res += self.cal(preSum, target)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "\n",
    "        n,m = len(matrix),len(matrix[0])\n",
    "        presum = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "\n",
    "        for i in range(1,n + 1):\n",
    "            for j in range(1,m + 1):\n",
    "                presum[i][j] = presum[i - 1][j] + presum[i][j - 1] - presum[i - 1][j - 1] + matrix[i - 1][j - 1]\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "\n",
    "        for x1 in range(1,n + 1):\n",
    "            for x2 in range(x1,n + 1):\n",
    "                dict1 = collections.defaultdict(int)\n",
    "\n",
    "                for r in range(1,m + 1):\n",
    "                    cur = presum[x2][r] - presum[x1 - 1][r]\n",
    "                    if cur == target:\n",
    "                        ans += 1\n",
    "                    \n",
    "                    ans += dict1[cur - target]\n",
    "                    dict1[cur] += 1\n",
    "        \n",
    "        return ans\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        for t in range(m):\n",
    "            rowsum = [0] * n\n",
    "            for b in range(t, m):\n",
    "                mp = defaultdict(int)\n",
    "                mp[0] = 1\n",
    "                colsum = 0\n",
    "                for c in range(n):\n",
    "                    rowsum[c] += matrix[b][c]\n",
    "                    colsum += rowsum[c]\n",
    "                    ans += mp.get(colsum - target, 0)\n",
    "                    mp[colsum] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def sumarraySum(nums, k):\n",
    "            mp = collections.Counter([0])\n",
    "            count = pre = 0\n",
    "            for x in nums:\n",
    "                pre += x\n",
    "                if pre - k in mp:\n",
    "                    count += mp[pre - k]\n",
    "                mp[pre] += 1\n",
    "            return count\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            total = [0] * n \n",
    "            for j in range(i, m):\n",
    "                for c in range(n):\n",
    "                    total[c] += matrix[j][c]\n",
    "                ans += sumarraySum(total, target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        # 二维前缀和\n",
    "        f = [[0]*(n + 1) for _ in range(m + 1)]\n",
    "        for i,row in enumerate(matrix):\n",
    "            for j,x in enumerate(row):\n",
    "                f[i + 1][j + 1] = f[i][j + 1] + f[i + 1][j] - f[i][j] + x\n",
    "        ans = 0\n",
    "        # 枚举子矩阵上下边界\n",
    "        for up in range(m):\n",
    "            for bo in range(up,m):\n",
    "                d = defaultdict(int)\n",
    "                # 枚举右边界，此处相当于两数之和\n",
    "                for i in range(n):\n",
    "                    # 右下角坐标 (bo,i) 左上角坐标 (up,0)\n",
    "                    s = f[bo + 1][i + 1] - f[up][i + 1]\n",
    "                    if s == target:\n",
    "                        ans += 1\n",
    "                    ans += d[s - target]\n",
    "                    d[s] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        R, C = len(matrix), len(matrix[0])\n",
    "        for row in matrix:\n",
    "            for c in range(C - 1):\n",
    "                row[c + 1] += row[c]\n",
    "\n",
    "        res = 0\n",
    "        for i in range(C):\n",
    "            for j in range(i, C): # turn to 1d array\n",
    "                nums = [matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0) for k in range(R)]\n",
    "                presum, d = 0, {0: 1}\n",
    "                for num in nums:\n",
    "                    presum += num\n",
    "                    if presum - target in d:\n",
    "                        res += d[presum - target]\n",
    "                    d[presum] = d.get(presum, 0) + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "\n",
    "        res = 0\n",
    "        for low in range(n):\n",
    "            sums = [0] * m\n",
    "            for high in range(low, n):\n",
    "                dict = {0 : 1}\n",
    "                tot  = 0\n",
    "                for r in range(m):\n",
    "                    sums[r] += matrix[high][r]\n",
    "                    tot += sums[r]\n",
    "                    if (cur := tot - target) in dict:\n",
    "                        res += dict[cur]\n",
    "                        #dict[cur] += 1\n",
    "                    if tot not in dict:\n",
    "                        dict[tot] = 1\n",
    "                    else:\n",
    "                        dict[tot] += 1\n",
    "                #print(dict)\n",
    "        \n",
    "        return res\n",
    "                    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        res = 0\n",
    "        \n",
    "        def prefixSum(nums,target):\n",
    "            n = len(nums)\n",
    "            prefix = 0\n",
    "            ans = 0\n",
    "            dic = defaultdict(int)\n",
    "            dic[0]=1\n",
    "            for i in nums:\n",
    "                prefix+=i\n",
    "                ans += dic[prefix-target]\n",
    "                dic[prefix]+=1\n",
    "            return ans\n",
    "        \n",
    "        for x in range(m):\n",
    "            nums = [0]*n\n",
    "            for i in range(x,m):\n",
    "                for j in range(n):\n",
    "                    nums[j]+=matrix[i][j]\n",
    "                res += prefixSum(nums,target)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix, target):\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for row in matrix:\n",
    "            for i in range(n - 1):\n",
    "                row[i + 1] += row[i]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                c = collections.defaultdict(int)\n",
    "                cur, c[0] = 0, 1\n",
    "                for k in range(m):\n",
    "                    cur += matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0)\n",
    "                    ans += c[cur - target]\n",
    "                    c[cur] += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def subarraySum(nums: List[int], k: int) -> int:\n",
    "            mp = Counter([0])\n",
    "            count = pre = 0\n",
    "            for x in nums:\n",
    "                pre += x\n",
    "                if pre - k in mp:\n",
    "                    count += mp[pre - k]\n",
    "                mp[pre] += 1\n",
    "            return count\n",
    "        \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        # 枚举上边界\n",
    "        for i in range(m):\n",
    "            total = [0] * n\n",
    "            # 枚举下边界\n",
    "            for j in range(i, m):\n",
    "                for c in range(n):\n",
    "                    # 更新每列的元素和\n",
    "                    total[c] += matrix[j][c]\n",
    "                ans += subarraySum(total, target)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def pref_sum(a: List[int]) -> None:\n",
    "            for i in range(1, len(a)):\n",
    "                a[i] += a[i - 1]\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for r in matrix:\n",
    "           pref_sum(r)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                cumu = 0\n",
    "                cnt = Counter()\n",
    "                cnt[0] = 1\n",
    "                for k in range(m):\n",
    "                    s = matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0)\n",
    "                    cumu += s\n",
    "                    ans += cnt[cumu - target]\n",
    "                    cnt[cumu] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class prefix_sum:\n",
    "    #二维前缀和\n",
    "    def __init__(self, mat: int):\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        self.qz=[[0]*(n+1) for _ in range(m+1)]\n",
    "        qz=self.qz\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                qz[i][j]=qz[i-1][j]+qz[i][j-1]-qz[i-1][j-1]+mat[i-1][j-1]\n",
    "\n",
    "    #查询以(r1,c1)为左上角，(r2,c2)为右下角的矩形区间内所有值的和\n",
    "    def find(self,r1,c1,r2,c2):  \n",
    "        qz=self.qz\n",
    "        return qz[r2+1][c2+1]-qz[r2+1][c1]-qz[r1][c2+1]+qz[r1][c1]\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        res=0\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        pre=prefix_sum(matrix)\n",
    "        for i in range(m):\n",
    "            for j in range(i,m):\n",
    "                d=defaultdict(int)\n",
    "                d[0]=1\n",
    "                for k in range(n):\n",
    "                    p=pre.find(i,0,j,k)\n",
    "                    res+=d[p-target]\n",
    "                    d[p]+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        R, C = len(matrix), len(matrix[0])\n",
    "        for row in matrix:\n",
    "            for c in range(C - 1):\n",
    "                row[c + 1] += row[c]\n",
    "\n",
    "        res = 0\n",
    "        for i in range(C):\n",
    "            for j in range(i, C): # turn to 1d array\n",
    "                nums = [matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0) for k in range(R)]\n",
    "                presum, d = 0, {0: 1}\n",
    "                for n in nums:\n",
    "                    presum += n\n",
    "                    if presum - target in d:\n",
    "                        res += d[presum - target]\n",
    "                    d[presum] = d.get(presum, 0) + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        res = 0\n",
    "        \n",
    "        def prefixSum(nums,target):\n",
    "            n = len(nums)\n",
    "            prefix = 0\n",
    "            ans = 0\n",
    "            dic = defaultdict(int)\n",
    "            dic[0]=1\n",
    "            for i in nums:\n",
    "                prefix+=i\n",
    "                ans += dic[prefix-target]\n",
    "                dic[prefix]+=1\n",
    "            return ans\n",
    "        \n",
    "        for x in range(m):\n",
    "            nums = [0]*n\n",
    "            for i in range(x,m):\n",
    "                for j in range(n):\n",
    "                    nums[j]+=matrix[i][j]\n",
    "                res += prefixSum(nums,target)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        suf = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                suf[i][j] = suf[i - 1][j] + suf[i][j - 1] - suf[i - 1][j - 1] + matrix[i - 1][j - 1]\n",
    "\n",
    "        ans = 0\n",
    "        for top in range(1, m + 1):\n",
    "            for bot in range(top, m + 1):\n",
    "                cnt = Counter()\n",
    "                cnt[0] = 1\n",
    "                for i in range(1, n + 1):\n",
    "                    x = suf[bot][i] - suf[top - 1][i]\n",
    "                    ans += cnt[x - target]\n",
    "                    cnt[x] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def subarraySum(nums: List[int], k: int) -> int:\n",
    "            mp = Counter([0])\n",
    "            count = pre = 0\n",
    "            for x in nums:\n",
    "                pre += x\n",
    "                if pre - k in mp:\n",
    "                    count += mp[pre - k]\n",
    "                mp[pre] += 1\n",
    "            print(mp)\n",
    "            return count\n",
    "        \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        # 枚举上边界\n",
    "        for i in range(m):\n",
    "            # print(f'上边界：{i}')\n",
    "\n",
    "            total = [0] * n\n",
    "            # 枚举下边界\n",
    "            for j in range(i, m):\n",
    "                # print(f'下边界: {j}')\n",
    "                for c in range(n):\n",
    "                    # 更新每列的元素和\n",
    "                    total[c] += matrix[j][c]\n",
    "                ans += subarraySum(total, target)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        Row, Col = len(matrix), len(matrix[0])\n",
    "\n",
    "        presum = [[0 for _ in range(Col + 1)] for _  in range(Row + 1)]\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                presum[r+1][c+1] = presum[r+1][c] + presum[r][c+1] - presum[r][c] + matrix[r][c]\n",
    "\n",
    "        res = 0\n",
    "        for U in range(0, Row + 1):\n",
    "            for D in range(U + 1, Row + 1):   #2块水平的木板夹住的区域\n",
    "                section_presum = defaultdict(int)       #2块水平木板中间，矩形右边界从左到右的前缀和\n",
    "                section_presum[0] = 1\n",
    "                for c in range(1, Col + 1):\n",
    "                    prefix = presum[D][c] - presum[U][c]\n",
    "                    res += section_presum[prefix - target]\n",
    "                    section_presum[prefix] += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "\n",
    "        # 二维前缀和\n",
    "        m , n = len(matrix),len(matrix[0])\n",
    "        s = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                s[i][j] = s[i-1][j]+s[i][j-1]-s[i-1][j-1] + matrix[i-1][j-1]\n",
    "        \n",
    "        res = 0\n",
    "\n",
    "        for top in range(m+1):\n",
    "            for bottom in range(top+1,m+1):\n",
    "                section_presum = defaultdict(int)\n",
    "                section_presum[0] = 1\n",
    "                for col in range(1, n + 1):\n",
    "                    # 一维前缀\n",
    "                    prefix = s[bottom][col] - s[top][col]\n",
    "                    # 如果s - target在哈希表中，则s - target = x，等价于s - x = target，\n",
    "                    res += section_presum[prefix - target]\n",
    "                    section_presum[prefix] += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        trans = m > n\n",
    "        if trans: m, n = n, m\n",
    "        colsum = [[0] * n for _ in range(m+1)]\n",
    "        for i, row in enumerate(matrix):\n",
    "            for j, x in enumerate(row):\n",
    "                if trans:\n",
    "                    colsum[j+1][i] = colsum[j][i] + x\n",
    "                else:\n",
    "                    colsum[i+1][j] = colsum[i][j] + x\n",
    "\n",
    "        ans = 0\n",
    "        for t in range(m):\n",
    "            for b in range(t+1, m+1):\n",
    "                mp = defaultdict(int)\n",
    "                mp[0] = 1\n",
    "                s = 0\n",
    "                for r in range(n):\n",
    "                    s += colsum[b][r] - colsum[t][r]\n",
    "                    ans += mp.get(s - target, 0)\n",
    "                    mp[s] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix, target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for row in matrix:\n",
    "            for i in range(1, n):\n",
    "                row[i] += row[i - 1]\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                c = collections.Counter({0: 1})\n",
    "                cur = 0\n",
    "                for k in range(m):\n",
    "                    cur += matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0)\n",
    "                    res += c[cur - target]\n",
    "                    c[cur] += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        # 二维前缀和\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        pre_sum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pre_sum[i + 1][j + 1] = pre_sum[i + 1][j] + pre_sum[i][j + 1] - pre_sum[i][j] + matrix[i][j]\n",
    "\n",
    "        # 结合一维前缀和\n",
    "        for up in range(m):\n",
    "            for down in range(up, m):\n",
    "                cnt = Counter([0])\n",
    "                sm = 0\n",
    "                for right in range(n):\n",
    "                    sm += pre_sum[down + 1][right + 1] + pre_sum[up][right] - pre_sum[up][right + 1] - pre_sum[down + 1][right]\n",
    "                    ans += cnt[sm - target]\n",
    "                    cnt[sm] += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix, target):\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for row in matrix:\n",
    "            for i in range(n - 1):\n",
    "                row[i + 1] += row[i]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                c = collections.defaultdict(int)\n",
    "                cur, c[0] = 0, 1\n",
    "                for k in range(m):\n",
    "                    cur += matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0)\n",
    "                    ans += c[cur - target]\n",
    "                    c[cur] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        cumsum = [[0]*(m+1) for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, m+1):\n",
    "                cumsum[i][j] = cumsum[i-1][j] + cumsum[i][j-1] - cumsum[i-1][j-1] + matrix[i-1][j-1]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(i, n+1):\n",
    "                mem = {0:1}\n",
    "                for k in range(1, m+1):\n",
    "                    cur = cumsum[j][k] - cumsum[i-1][k]\n",
    "                    ans += mem.get(cur-target, 0)\n",
    "                    mem[cur] = mem.get(cur, 0) + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class PreFixSumMatrix:\n",
    "    def __init__(self, mat):\n",
    "        self.mat = mat\n",
    "        # 二维前缀和\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        self.pre = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                self.pre[i + 1][j + 1] = self.pre[i][j + 1] + \\\n",
    "                    self.pre[i + 1][j] - self.pre[i][j] + mat[i][j]\n",
    "\n",
    "    def query(self, xa, ya, xb, yb):\n",
    "        # 二维子矩阵和查询，索引从 0 开始，左上角 [xa, ya] 右下角 [xb, yb]\n",
    "        return self.pre[xb + 1][yb + 1] - self.pre[xb +\n",
    "                                                   1][ya] - self.pre[xa][yb + 1] + self.pre[xa][ya]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        pre = PreFixSumMatrix(matrix)\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(i, m):\n",
    "                dct = defaultdict(int)\n",
    "                dct[0] = 1\n",
    "                for k in range(n):\n",
    "                    cur = pre.query(i, 0, j, k)\n",
    "                    ans += dct[cur-target]\n",
    "                    dct[cur] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        # 构建二维前缀和\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        prefix = [[0 for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1,n+1):\n",
    "                prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] + matrix[i-1][j-1] - prefix[i-1][j-1]\n",
    "        print(prefix)\n",
    "        # 遍历top, bottom, right\n",
    "        # 哈希查找left\n",
    "        ans = 0\n",
    "        for top in range(1, m+1): \n",
    "            for bottom in range(top, m+1):  \n",
    "                di = {} \n",
    "                for right in range(0, n+1): \n",
    "                    cur = prefix[bottom][right] - prefix[top-1][right]\n",
    "                    if cur - target in di: \n",
    "                        ans += di[cur - target]  \n",
    "                    if cur in di:\n",
    "                        di[cur] += 1\n",
    "                    else:\n",
    "                        di[cur] = 1\n",
    "        return ans  \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "presum = [[0] * 100 for _ in range(100)]\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                p1 = presum[i - 1][j] if i > 0 else 0\n",
    "                p2 = presum[i][j - 1] if j > 0 else 0\n",
    "                p3 = presum[i - 1][j - 1] if i > 0 and j > 0 else 0\n",
    "                presum[i][j] = matrix[i][j] + p1 + p2 - p3\n",
    "\n",
    "        ret = 0\n",
    "        for x1 in range(m):\n",
    "            for x2 in range(x1, m):\n",
    "                areas = [0]\n",
    "\n",
    "                for y in range(n):\n",
    "                    p1 = presum[x1 - 1][y] if x1 > 0 else 0\n",
    "                    a = presum[x2][y] - p1\n",
    "                    areas.append(a)\n",
    "\n",
    "                cnts = Counter(areas)\n",
    "\n",
    "                for a in areas:\n",
    "                    cnts[a] -= 1\n",
    "                    ret += cnts[a + target]\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def get_area(i1, j1, i2, j2):\n",
    "            return dp[i2 + 1][j2 + 1] - dp[i1][j2 + 1] - dp[i2 + 1][j1] + dp[i1][j1]\n",
    "\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]  # 2D pre-sum\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dp[i + 1][j + 1] = matrix[i][j] + dp[i][j + 1] + dp[i + 1][j] - dp[i][j]\n",
    "        cnt = 0\n",
    "        for l in range(n):\n",
    "            for r in range(l, n):\n",
    "                counter = defaultdict(int)\n",
    "                counter[0] = 1\n",
    "                for down in range(m):\n",
    "                    area = get_area(0, l, down, r)\n",
    "                    cnt += counter[area - target]\n",
    "                    counter[area] += 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans, j = 0, n-1\n",
    "        for i in range(n):\n",
    "            if nums[i] * 2 > target:\n",
    "                break\n",
    "            while nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            ans += pow(2, j - i,MOD )\n",
    "        return ans % MOD\n",
    "\n",
    "\n",
    "       \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        right, ans, mod=n-1,0, 10**9+7\n",
    "        for left,c in enumerate(nums):\n",
    "            while right>=left and c+nums[right]>target:\n",
    "                right-=1\n",
    "            if right>=left:\n",
    "                # ans+=(1<<(right-left))%mod  # left以外的每个数字选或不选\n",
    "                ans=(ans%mod+pow(2,right-left,mod))%mod\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "\n",
    "        nums.sort()\n",
    "        ans = j = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] * 2 > target:\n",
    "                break\n",
    "            # 指针回撤\n",
    "            # while j == n or nums[i] + nums[j] > target:\n",
    "            #     j -= 1\n",
    "            # while j < n and nums[i] + nums[j] <= target:\n",
    "            #     j += 1\n",
    "            j = bisect.bisect_right(nums, target - nums[i])\n",
    "            ans += pow(2, j - i - 1, MOD)\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans, j = 0, n-1\n",
    "        for i in range(n):\n",
    "            if nums[i] * 2 > target:\n",
    "                break\n",
    "            while nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            ans += pow(2, j - i, MOD)\n",
    "        return ans % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        i, j = 0, len(nums) - 1\n",
    "        ans = 0\n",
    "        while i <= j:\n",
    "            if nums[i] + nums[j] <= target:\n",
    "                ans += 1 << (j - i)\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return ans % (10**9 + 7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fast_pow(self, n, a):\n",
    "        if a==0: return 1\n",
    "        if a==1: return n\n",
    "        if a%2: return self.fast_pow(n, a//2)**2*n% 1000000007\n",
    "        return self.fast_pow(n, a//2)**2% 1000000007\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            p = bisect.bisect_right(nums, target-nums[i])\n",
    "            if p>i: res += self.fast_pow(2, p-i-1) % 1000000007\n",
    "        return res%1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans, j = 0,0\n",
    "        for i in range(n):\n",
    "            if nums[i] * 2 > target:\n",
    "                break\n",
    "            while j == n or nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            while j < n and nums[i] + nums[j] <= target:\n",
    "                j += 1\n",
    "            ans += pow(2, j - i - 1,MOD )\n",
    "        return ans % MOD\n",
    "\n",
    "\n",
    "       \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        r = n - 1\n",
    "        for l, x in enumerate(nums):\n",
    "            if x * 2 > target:\n",
    "                break\n",
    "            while r > l and x + nums[r] > target:\n",
    "                r -= 1\n",
    "            ans += pow(2, r - l, MOD)\n",
    "        return ans % MOD\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        mod = 10**9 + 7\n",
    "        for i, x in enumerate(nums):\n",
    "            if x + x > target:\n",
    "                break\n",
    "            l = i\n",
    "            r = n - 1\n",
    "            while l < r:\n",
    "                mid = l + r + 1 >> 1\n",
    "                if nums[mid] <= target - x:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            if nums[r] <= target - x:\n",
    "                res = (res + pow(2, r - i, mod)) % mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = j = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] * 2 > target:\n",
    "                break\n",
    "            # 指针回撤\n",
    "            while j == n or nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            while j < n and nums[i] + nums[j] <= target:\n",
    "                j += 1\n",
    "            ans += pow(2, j - i - 1, MOD)\n",
    "        return ans % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        MOD = 1000000007\n",
    "\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            if nums[i] >= target:\n",
    "                continue\n",
    "            k = bisect.bisect_right(nums, target-nums[i], 0, i+1)\n",
    "            if k > i:\n",
    "                ans += 1\n",
    "                k -= 1\n",
    "            if k == 0:\n",
    "                continue\n",
    "            ans += pow(2, i, MOD) - pow(2, i-k, MOD)\n",
    "        \n",
    "        return ans % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        mod = 1000000007\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        # 枚举第一个元素\n",
    "        p = [0] * n\n",
    "        p[0] = 1\n",
    "        for i in range(1, n):\n",
    "            p[i] = (p[i - 1] << 1) % mod\n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "            if x > target // 2:\n",
    "                break\n",
    "            # 枚举到的数字本身也算作和自己匹配的一种\n",
    "            l, r = i, n - 1\n",
    "            while l < r:\n",
    "                mid = l + ((r - l) >> 1) + 1\n",
    "                if nums[mid] > target - x:\n",
    "                    r = mid - 1\n",
    "                else:\n",
    "                    l = mid\n",
    "            if nums[l] <= target - x:\n",
    "                ans = (ans + p[l - i]) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        l, r = 0, len(nums) - 1\n",
    "        res = 0\n",
    "        while l <= r:\n",
    "            if nums[l] + nums[r] > target:\n",
    "                r -= 1\n",
    "            else:\n",
    "                res = (res + pow(2, r - l, mod)) % mod\n",
    "                l += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#from scipy.special import comb\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()        \n",
    "        m=len(nums)\n",
    "        index=bisect.bisect_left(nums,target//2+1)\n",
    "        c=0\n",
    "\n",
    "        for i in range(index):\n",
    "            #if nums[i]*2>target:\n",
    "            #    break\n",
    "            j=bisect.bisect_right(nums,target-nums[i])\n",
    "            #if j!=0:\n",
    "            c=c+pow(2,j-i-1,10**9+7)\n",
    "            #print(i,j)\n",
    "\n",
    "        return int(c%(10**9+7))\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        res, mod = 0, (10**9 + 7)\n",
    "\n",
    "        left, right = 0, len(nums) - 1\n",
    "        while  left <= right:\n",
    "            if (nums[left] + nums[right]) > target:\n",
    "                right -= 1\n",
    "            else:\n",
    "                res += 1 << (right - left)\n",
    "                left += 1\n",
    "        return res % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "\n",
    "        f = [1] + [0] * len(nums)\n",
    "\n",
    "        for i in range(1, len(f)):\n",
    "            f[i] = f[i - 1] * 2 % mod\n",
    "\n",
    "        j = len(nums) - 1\n",
    "        for i, n in enumerate(nums):\n",
    "            if 2 * n > target:\n",
    "                break\n",
    "\n",
    "            while i <= j and nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            res = (res + f[j - i]) % mod\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: list[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        left = 0\n",
    "        right = len(nums)-1\n",
    "        mod = 1000000007\n",
    "        tmp = len(nums) * [0]\n",
    "        tmp[0] = 1\n",
    "        i = 1\n",
    "        cnt = 0\n",
    "        while(i<len(tmp)):\n",
    "            tmp[i] = (tmp[i-1] * 2) % mod\n",
    "            i+=1\n",
    "        while left<=right:\n",
    "            if nums[left]+nums[right]>target:\n",
    "                right-=1\n",
    "            else:\n",
    "                cnt = (cnt + tmp[right-left])%mod\n",
    "                left += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        P = 1e9+7\n",
    "        n = len(nums)\n",
    "        # 记录2的i次方\n",
    "        f = [1]+[0]*(n-1)\n",
    "        for i in range(1,n):\n",
    "            f[i] = f[i-1]*2%P # 在后面用于相乘，所以可以提前取模\n",
    "\n",
    "        nums.sort()\n",
    "        cnt = 0\n",
    "        for i,num in enumerate(nums):\n",
    "            if nums[i] * 2 > target:\n",
    "                break\n",
    "            idx = bisect_right(nums,target-nums[i])-1 #大于阈值的第一个-1\n",
    "            if idx >= i:\n",
    "                cnt+=f[idx-i]\n",
    "        return int(cnt%P)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        if nums[0] * 2 > target:\n",
    "            return 0\n",
    "            \n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        res = 0\n",
    "        while left <= right:\n",
    "            if nums[left] + nums[right] <= target:\n",
    "                res += 1 << (right-left)\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return res%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        i, j = 0, len(nums) - 1\n",
    "        ans = 0\n",
    "        while i <= j:\n",
    "            if nums[i] + nums[j] <= target:\n",
    "                ans += 2**(j - i)\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return ans % (10**9 + 7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        if nums[0] * 2 > target:\n",
    "            return 0\n",
    "        res = 0\n",
    "        l = 0\n",
    "        r = len(nums)-1\n",
    "        while l <= r:\n",
    "            if nums[l] + nums[r] <= target:\n",
    "                res += 2**(r-l)\n",
    "                l += 1\n",
    "            else:\n",
    "                r -= 1\n",
    "        return res%(10**9+7)\n",
    "        \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        left, right = 0, n-1\n",
    "        if nums[0]*2 > target:return ans\n",
    "        while left <= right:\n",
    "            if nums[left]+nums[right] <= target:\n",
    "                ans += 1<<(right-left)\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return ans%(10**9+7)\n",
    "        '''\n",
    "        ans = 0\n",
    "        pre = n-1\n",
    "        for i in range(n):\n",
    "            if nums[i]*2 > target:break\n",
    "            if i > 0 and nums[i-1] == nums[i]:\n",
    "                ans += 2**(right-i)\n",
    "                continue\n",
    "            temp = target - nums[i]\n",
    "            left, right = i, pre\n",
    "            while left <= right:\n",
    "                mid = left + (right-left)//2\n",
    "                if nums[mid] > temp:\n",
    "                    right = mid-1\n",
    "                else:\n",
    "                    left = mid+1\n",
    "            pre = right\n",
    "            ans += 2**(right-i)\n",
    "\n",
    "        return ans%(10**9+7)\n",
    "        '''\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        if nums[0] * 2 > target:\n",
    "            return 0\n",
    "            \n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        res = 0\n",
    "        while left <= right:\n",
    "            if nums[left] + nums[right] <= target:\n",
    "                res += 2**(right-left)\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return res%(10**9+7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        if nums[0]*2>target:\n",
    "            return 0\n",
    "        count=0    # 记录满足的子序列的个数\n",
    "        i,j=0,len(nums)-1\n",
    "        while i<=j:\n",
    "            if nums[i]+nums[j]<=target:  # 取得子序列的最小值和最大值，与target进行比较\n",
    "                count+=2**(j-i)\n",
    "                i+=1\n",
    "            else:\n",
    "                j-=1\n",
    "        return count%(10**9+7) # 最终返回满足的子序列的总数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]*2 > target:\n",
    "                break\n",
    "            j = bisect.bisect_left(nums, target-nums[i]+1)-1\n",
    "            # print(nums[i], j)\n",
    "            if j >= i:\n",
    "                ans += 1 << (j-i)\n",
    "        \n",
    "        return ans % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        if nums[0] > target:return 0\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        while left <= right:\n",
    "            if nums[left] + nums[right] <= target:\n",
    "                ans += 2 **(right - left) #[left,right]区间内的全排序组合个数\n",
    "                left += 1\n",
    "            else:right -= 1\n",
    "        return ans % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]*2 > target:\n",
    "                break\n",
    "            j = bisect.bisect_right(nums, target-nums[i])-1\n",
    "            # print(nums[i], j)\n",
    "            if j >= i:\n",
    "                ans += 1 << (j-i)\n",
    "        \n",
    "        return ans % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        left, right = 0, len(nums) - 1\n",
    "        # 寻找右边界开始满足的端点\n",
    "        res = 0\n",
    "        while left <= right:\n",
    "            # 该区间的满足最大最小\n",
    "            if nums[left] + nums[right] <= target:\n",
    "                res += 2**(right - left)\n",
    "                res %= 10**9 + 7\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return int(res % (10**9 + 7))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "        if nums[0] * 2 > target:\n",
    "            return 0\n",
    "        left, right = 0, len(nums) - 1\n",
    "        while left <= right:\n",
    "            if nums[left] + nums[right] <= target:\n",
    "                res += 2 ** (right-left) \n",
    "                left += 1\n",
    "            elif nums[left] + nums[right] > target:\n",
    "                right -= 1\n",
    "        return res % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        r = len(nums) - 1\n",
    "        for i, left in enumerate(nums):\n",
    "            while (left + nums[r] > target) and i <= r:\n",
    "                r -= 1\n",
    "            if i <= r:\n",
    "                res += (2 ** (r - i)) \n",
    "        return res % mod\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        right, ans, mod=n-1,0, 10**9+7\n",
    "        for left,c in enumerate(nums):\n",
    "            while right>=left and c+nums[right]>target:\n",
    "                right-=1\n",
    "            if right>=left:\n",
    "                # ans+=(1<<(right-left))%mod  # left以外的每个数字选或不选\n",
    "                ans=(ans%mod+pow(2,right-left,mod))%mod\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        right = n - 1\n",
    "        for i in range(n):\n",
    "            if(i > right):\n",
    "                break\n",
    "            left = i + 1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)>>1\n",
    "                if(nums[i] + nums[mid] <= target):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            result += (1<<(right-i))-1\n",
    "            if(nums[i]*2<= target):\n",
    "                result += 1\n",
    "        return result % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        mod = 10**9+7\n",
    "        r = len(nums)-1\n",
    "        l = 0\n",
    "        ans = 0\n",
    "        while r>=0:\n",
    "            while l<=r and nums[l]+nums[r]<=target:\n",
    "                l += 1\n",
    "            # print(ans, l, r, (1<<r), (1<<(max(r-l, 0))))\n",
    "            if l>r:\n",
    "                ans = (ans + (1<<r)) % mod\n",
    "            else:\n",
    "                ans = (ans + (1<<r) - (1<<(max(r-l, 0)))) % mod\n",
    "            r -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        right = n - 1\n",
    "        for i in range(n):\n",
    "            if(i > right):\n",
    "                break\n",
    "            left = i + 1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)>>1\n",
    "                if(nums[i] + nums[mid] <= target):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            result += 2**(right-i)-1\n",
    "            if(nums[i]*2<= target):\n",
    "                result += 1\n",
    "        return result % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "\n",
    "        nums.sort()\n",
    "        l = 0\n",
    "        r = len(nums) - 1\n",
    "        count = 0\n",
    "        if nums[0] * 2 > target:\n",
    "            return 0\n",
    "        while l <= r:\n",
    "            if nums[l] + nums[r] > target:\n",
    "                r -= 1\n",
    "            else:\n",
    "                count += 2**(r-l)\n",
    "                l += 1\n",
    "        return count % (10**9+7)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        if nums[0] * 2 > target:\n",
    "            return 0\n",
    "\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        ans = 0\n",
    "        while left<=right:\n",
    "            if nums[left] + nums[right] <= target:\n",
    "                ans += 2**(right-left)\n",
    "                left += 1\n",
    "            else:\n",
    "                right -=1 \n",
    "        return ans % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        \"\"\" nums.sort()\n",
    "        n = len(nums)\n",
    "        i = 0 \n",
    "        j = 0\n",
    "        res = 0\n",
    "        MOD = 10**9+7\n",
    "        \n",
    "        while i < n and nums[i] <= target/2:\n",
    "            j = bisect_right(nums,target-nums[i]) - 1\n",
    "            res += 2**(j-i)\n",
    "            i += 1\n",
    "        return res%MOD \"\"\"\n",
    "        MOD = 10**9+7\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] * 2 > target:\n",
    "                break\n",
    "            j = bisect.bisect_right(nums, target - nums[i])\n",
    "            ans += pow(2, j - i - 1, MOD)\n",
    "        return ans % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        right, ans, mod=n-1,0, 10**9+7\n",
    "        for left,c in enumerate(nums):\n",
    "            while right>=left and c+nums[right]>target:\n",
    "                right-=1\n",
    "            if right>=left:\n",
    "                # ans+=(1<<(right-left))%mod  # left以外的每个数字选或不选\n",
    "                ans=(ans%mod+pow(2,right-left,mod))%mod\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        i = 0 \n",
    "        j = 0\n",
    "        res = 0\n",
    "        MOD = 10**9+7\n",
    "        \n",
    "        while i < n and nums[i] <= target/2:\n",
    "            j = bisect_left(nums,target-nums[i]+1) - 1\n",
    "            #res += 2**(j-i)\n",
    "            res += pow(2, j - i, MOD)\n",
    "            i += 1\n",
    "        return res%MOD\n",
    "\n",
    "\n",
    "        \"\"\" MOD = 10**9+7 #儿酒醉-排序+二分\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] * 2 > target:\n",
    "                break\n",
    "            j = bisect.bisect_right(nums, target - nums[i])\n",
    "            ans += pow(2, j - i - 1, MOD)\n",
    "        return ans % MOD \"\"\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        right, ans, mod=n-1,0, 10**9+7\n",
    "        for left,c in enumerate(nums):\n",
    "            while right>=left and c+nums[right]>target:\n",
    "                right-=1\n",
    "            if right>=left:\n",
    "                ans=(ans%mod+pow(2,right-left,mod))%mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, a: List[int], t: int) -> int:\n",
    "        ans = 0\n",
    "        m = 10**9 + 7 \n",
    "        a.sort()\n",
    "        n = len(a)\n",
    "        j = n - 1\n",
    "        for i in range(n):\n",
    "            if i>j:\n",
    "                return ans%m \n",
    "            while a[i] + a[j] > t:\n",
    "                j -= 1\n",
    "                if j<i:\n",
    "                    return ans%m  \n",
    "            ans += pow(2, j-i, m)\n",
    "        return ans%m\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import bisect\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        print(nums,n)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            if nums[i]*2>target:\n",
    "                break\n",
    "            idx=bisect.bisect_right(nums,target-nums[i])\n",
    "            # print(i,idx)\n",
    "            if idx>i:\n",
    "                ans+=2**(idx-1-i)\n",
    "        return int(ans%(10**9+7))\n",
    "        \n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n= len(nums)\n",
    "        l, r = 0, n-1\n",
    "        ans=0\n",
    "        while l<=r:\n",
    "            if nums[l]+nums[r]<=target:\n",
    "                ans+=1<<(r-l)\n",
    "                l+=1\n",
    "            else:\n",
    "                r-=1\n",
    "        return ans%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        ans = 0\n",
    "        cnt = [0] * (n + 1)\n",
    "        cnt[1] = 1\n",
    "        nums = sorted(nums)\n",
    "        for i in range(2,n+1):\n",
    "            cnt[i] = (cnt[i-1]*2+1)%1000000007\n",
    "        while left <= right:\n",
    "            if nums[left] + nums[right] <= target:\n",
    "                ans = ans + cnt[right-left+1]-cnt[right-left]\n",
    "                ans = ans % 1000000007\n",
    "                left = left + 1\n",
    "            else:\n",
    "                right = right - 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        #解题思路：\n",
    "        #注意要求是子序列，因此先进行排序，其次进行二分\n",
    "\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        right, ans, mod=n-1,0, 10**9+7\n",
    "        for left,c in enumerate(nums):\n",
    "            while right>=left and c+nums[right]>target:\n",
    "                right-=1\n",
    "            if right>=left:\n",
    "                # ans+=(1<<(right-left))%mod  # left以外的每个数字选或不选\n",
    "                ans=(ans%mod+pow(2,right-left,mod))%mod\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            lo = i\n",
    "            hi = n \n",
    "            k = i - 1\n",
    "            while lo < hi:\n",
    "                mi = (lo + hi)//2 \n",
    "                if nums[i] + nums[mi] <= target:\n",
    "                    lo = mi + 1 \n",
    "                else:\n",
    "                    hi = mi\n",
    "            if lo - i > 0:\n",
    "                ans += pow(2, lo - i-1,10**9 + 7)\n",
    "        return ans %(10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        \n",
    "        def search(nums, value):\n",
    "            lo, hi = 0, len(nums)\n",
    "            while lo < hi:\n",
    "                mid = lo + (hi - lo) // 2\n",
    "                if nums[mid] <= value:\n",
    "                    lo = mid + 1\n",
    "                else:\n",
    "                    hi = mid\n",
    "            return lo\n",
    "        \n",
    "        def power(x, n):\n",
    "            MOD = 10 ** 9 + 7\n",
    "            t = x\n",
    "            ans = 1\n",
    "            while n:\n",
    "                if n % 2:\n",
    "                    ans = ans * t % MOD\n",
    "                t = (t * t) % MOD\n",
    "                n //= 2\n",
    "            return ans \n",
    "\n",
    "\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "            if x * 2 > target:\n",
    "                break\n",
    "            index = search(nums, target - x)\n",
    "            ans += power(2, index - i - 1)\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [0] * 100005\n",
    "        f[0] = 1\n",
    "        for i in range(1, n):\n",
    "            f[i] = f[i - 1] * 2 % MOD\n",
    "        nums = sorted(nums)\n",
    "        ans = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if 2 * num > target:\n",
    "                break\n",
    "            idx = bisect_right(nums, target - num) - 1\n",
    "            ans = (ans + f[idx - i ]) % MOD\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums = sorted(nums)\n",
    "        result = 0\n",
    "        mod = (10**9 + 7)\n",
    "        r = len(nums) - 1\n",
    "        for i, left in enumerate (nums):\n",
    "            while left + nums[r] > target and i <= r:\n",
    "                r -= 1\n",
    "            if i <= r:\n",
    "                result += 2**(r-i)\n",
    "                result %= mod\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        P = 10**9 + 7\n",
    "        f = [1] + [0] * (n - 1)\n",
    "        for i in range(1, n):\n",
    "            f[i] = f[i - 1] * 2 % P\n",
    "\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if nums[i] * 2 > target:\n",
    "                break\n",
    "            maxValue = target - nums[i]\n",
    "            pos = bisect.bisect_right(nums, maxValue) - 1\n",
    "            contribute = f[pos - i] if pos >= i else 0\n",
    "            ans += contribute\n",
    "        \n",
    "        return ans % P\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "\n",
    "        f = [1] + [0] * len(nums)\n",
    "\n",
    "        for i in range(1, len(f)):\n",
    "            f[i] = f[i - 1] * 2 % mod\n",
    "\n",
    "        j = len(nums) - 1\n",
    "        for i, n in enumerate(nums):\n",
    "            if 2 * n > target:\n",
    "                break\n",
    "\n",
    "            while i <= j and nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            res += f[j - i]\n",
    "            res %= mod\n",
    "        \n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        P = 10**9 + 7\n",
    "        f = [1] + [0] * (n - 1)\n",
    "        for i in range(1, n):\n",
    "            f[i] = f[i - 1] * 2 % P\n",
    "\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if nums[i] * 2 > target:\n",
    "                break\n",
    "            maxValue = target - nums[i]\n",
    "            pos = bisect.bisect_right(nums, maxValue) - 1\n",
    "            contribute = f[pos - i] if pos >= i else 0\n",
    "            ans += contribute\n",
    "        \n",
    "        return ans % P"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        f = [1] + [0] * (len(nums) - 1)\n",
    "        for i in range(1, len(nums)):\n",
    "            f[i] = f[i - 1] * 2 % MOD\n",
    "        for r in range(len(nums) - 1, -1, -1):\n",
    "            while l <= r and nums[l] + nums[r] <= target:\n",
    "                l += 1\n",
    "            ans = (ans + f[r] - (f[r - l] if l <= r else 0)) % MOD\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        mod = int(10**9+7)\n",
    "        ret = 0\n",
    "        l, r = 0, len(nums)-1\n",
    "        while l<=r:\n",
    "            if nums[l]+nums[r]>target:\n",
    "                r -= 1\n",
    "            else:\n",
    "                ret = (ret + (1<<(r-l)))%mod\n",
    "                l+=1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        right = n - 1\n",
    "        for i in range(n):\n",
    "            if(i > right):\n",
    "                break\n",
    "            left = i + 1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)>>1\n",
    "                if(nums[i] + nums[mid] <= target):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            result += (1<<(right-i))-1\n",
    "            if(nums[i]*2<= target):\n",
    "                result += 1\n",
    "        return result % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        '''\n",
    "        ans = 0\n",
    "        left, right = 0, n-1\n",
    "        if nums[0]*2 > target:return ans\n",
    "        while left <= right:\n",
    "            if nums[left]+nums[right] <= target:\n",
    "                ans += 1<<(right-left)\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return ans%(10**9+7)\n",
    "        '''\n",
    "        ans = 0\n",
    "        pre = n-1\n",
    "        for i in range(n):\n",
    "            if nums[i]*2 > target:break\n",
    "            if i > 0 and nums[i-1] == nums[i]:\n",
    "                ans += 2**(right-i)\n",
    "                continue\n",
    "            temp = target - nums[i]\n",
    "            left, right = i, pre\n",
    "            while left <= right:\n",
    "                mid = left + (right-left)//2\n",
    "                if nums[mid] > temp:\n",
    "                    right = mid-1\n",
    "                else:\n",
    "                    left = mid+1\n",
    "            pre = right\n",
    "            ans += 1<<(right-i)\n",
    "\n",
    "        return ans%(10**9+7)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        M = 10**9+7\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        right = n - 1\n",
    "        for i in range(n):\n",
    "            if(i > right):\n",
    "                break\n",
    "            left = i + 1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)>>1\n",
    "                if(nums[i] + nums[mid] <= target):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            result += (1<<(right-i))-1\n",
    "            if(nums[i]*2<= target):\n",
    "                result += 1\n",
    "        return result % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        M = 10**9+7\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        right = n - 1\n",
    "        for i in range(n):\n",
    "            if(i > right):\n",
    "                break\n",
    "            left = i + 1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)>>1\n",
    "                if(nums[i] + nums[mid] <= target):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            result += (1<<(right-i))-1\n",
    "            if(nums[i]*2<= target):\n",
    "                result += 1\n",
    "        return result % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        right = n - 1\n",
    "        for i in range(n):\n",
    "            if(i > right):\n",
    "                break\n",
    "            left = i + 1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)>>1\n",
    "                if(nums[i] + nums[mid] <= target):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            result += 2**(right-i)-1\n",
    "            if(nums[i]*2<= target):\n",
    "                result += 1\n",
    "        return result % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        if nums[0]*2>target:\n",
    "            return 0\n",
    "        count=0    # 记录满足的子序列的个数\n",
    "        i,j=0,len(nums)-1\n",
    "        while i<=j:\n",
    "            if nums[i]+nums[j]<=target:  # 取得子序列的最小值和最大值，与target进行比较\n",
    "                # count+=2**(j-i)\n",
    "                count += 1<<(j-i)   # 利用位运算，提高效率\n",
    "                i+=1\n",
    "            else:\n",
    "                j-=1\n",
    "        return count%(10**9+7) # 最终返回满足的子序列的总数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if nums[i]*2 > target:break\n",
    "            temp = target - nums[i]\n",
    "            left, right = 0, n-1\n",
    "            while left <= right:\n",
    "                mid = left + (right-left)//2\n",
    "                if nums[mid] > temp:\n",
    "                    right = mid-1\n",
    "                else:\n",
    "                    left = mid+1\n",
    "\n",
    "            ans += 2**(right-i)\n",
    "\n",
    "        return ans%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        # print(nums)\n",
    "        result=0\n",
    "        for start in range(len(nums)):\n",
    "            if nums[start]>target:\n",
    "                break\n",
    "            elif nums[start]*2<=target:\n",
    "                count=1\n",
    "            else:\n",
    "                count=0\n",
    "\n",
    "            left = start\n",
    "            right = len(nums)-1\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                if nums[mid] + nums[start] > target:\n",
    "                    right = mid - 1\n",
    "                elif nums[mid] + nums[start] < target:\n",
    "                    if mid+1<len(nums) and nums[mid+1] + nums[start]>target:\n",
    "                        break\n",
    "                    left = mid + 1\n",
    "                elif mid+1<len(nums) and nums[mid] + nums[start] == target and nums[mid+1] + nums[start] == target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    break\n",
    "            count+=mid-start\n",
    "            # print(count)\n",
    "            if count>0:\n",
    "                result+=2**(count-1)\n",
    "        result=result%(10**9 + 7)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        if nums[0]*2>target:\n",
    "          return 0\n",
    "        l=0\n",
    "        r=len(nums)-1\n",
    "        res=0\n",
    "        while l<=r:\n",
    "            if nums[l]+nums[r]<=target:\n",
    "                res+=2**(r-l);\n",
    "                l+=1\n",
    "            else:\n",
    "                r-=1\n",
    "        return res%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        mod = 10**9 +7\n",
    "        res = 0 \n",
    "        for left in range(n):\n",
    "            right = bisect.bisect_right(nums, target - nums[left])-1\n",
    "            if right >= left:\n",
    "                res += pow(2, right - left)\n",
    "        return res % (mod)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import bisect\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        print(nums,n)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            idx=bisect.bisect_right(nums,target-nums[i])\n",
    "            # print(i,idx)\n",
    "            if idx>i:\n",
    "                ans+=2**(idx-1-i)\n",
    "        return int(ans%(10**9+7))\n",
    "        \n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#1 -> 1\n",
    "#2 -> 2\n",
    "#3 -> 6\n",
    "#4 -> 10\n",
    "#滑窗 + 求和\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def sumd(self, n):\n",
    "        return (1 + n) * n // 2\n",
    "\n",
    "    def numSub(self, s: str) -> int:\n",
    "        cnt, ans = 0, 0 \n",
    "        for i in s:\n",
    "            if i == '1':\n",
    "                cnt += 1\n",
    "            else:\n",
    "                ans += self.sumd(cnt)\n",
    "                cnt = 0\n",
    "        if s[len(s) - 1] == '1':\n",
    "            ans += self.sumd(cnt)\n",
    "        return ans % MOD "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        ones = 0\n",
    "        result = 0\n",
    "        s += '0'\n",
    "        for c in s:\n",
    "            if(c == '1'):\n",
    "                ones += 1\n",
    "            else:\n",
    "                result += ones * (ones+1) // 2\n",
    "                ones = 0\n",
    "        return result % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        start = 0\n",
    "        end = 0\n",
    "        result = 0\n",
    "        s = '0' + s\n",
    "        length = len(s)\n",
    "        while (start < length):\n",
    "            while start < length and s[start] == '0':\n",
    "                start += 1\n",
    "            end = start\n",
    "            while end < length and s[end] == '1':\n",
    "                end += 1\n",
    "\n",
    "            temp = end - start\n",
    "            result += (1 + temp) * temp // 2 % 1000000007\n",
    "\n",
    "            start = end\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        ones = 0\n",
    "        result = 0\n",
    "        s += '0'\n",
    "        for c in s:\n",
    "            if(c == '1'):\n",
    "                ones += 1\n",
    "            else:\n",
    "                result += ones * (ones+1) // 2\n",
    "                ones = 0\n",
    "        return result % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        n = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '0':\n",
    "                ans += n/2*(1+n)\n",
    "                n = 0\n",
    "            elif s[i] == \"1\":\n",
    "                n += 1\n",
    "        ans += n / 2 * (1 + n)\n",
    "        ans = int(ans)\n",
    "        return ans % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        j = 0\n",
    "        ans = 0\n",
    "        for i, x in enumerate(s):\n",
    "            if x == '0':\n",
    "                j = i + 1\n",
    "                continue\n",
    "            ans += i - j + 1\n",
    "            ans %= 1000000007\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        total, consecutive = 0, 0\n",
    "        length = len(s)\n",
    "        for i in range(length):\n",
    "            if s[i] == '0':\n",
    "                total += consecutive * (consecutive + 1) // 2\n",
    "                consecutive = 0\n",
    "            else:\n",
    "                consecutive += 1\n",
    "        \n",
    "        total += consecutive * (consecutive + 1) // 2\n",
    "        total %= (10**9 + 7)\n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#1 -> 1\n",
    "#2 -> 2\n",
    "#3 -> 6\n",
    "#4 -> 10\n",
    "#遍历 + 求和\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def sumd(self, n):\n",
    "        return (1 + n) * n // 2\n",
    "\n",
    "    def numSub(self, s: str) -> int:\n",
    "        cnt, ans = 0, 0 \n",
    "        for i in s:\n",
    "            if i == '1':\n",
    "                cnt += 1\n",
    "            else:\n",
    "                ans += self.sumd(cnt)\n",
    "                cnt = 0\n",
    "        if s[len(s) - 1] == '1':\n",
    "            ans += self.sumd(cnt)\n",
    "        return ans % MOD "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        total, consecutive = 0, 0\n",
    "        length = len(s)\n",
    "        for i in range(length):\n",
    "            if s[i] == '0':\n",
    "                total += consecutive * (consecutive + 1) // 2\n",
    "                consecutive = 0\n",
    "            else:\n",
    "                consecutive += 1\n",
    "        \n",
    "        total += consecutive * (consecutive + 1) // 2\n",
    "        total %= (10**9 + 7)\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        x=0\n",
    "        ans=0\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            if s[i]=='0':\n",
    "                x=0\n",
    "            else:\n",
    "                x+=1\n",
    "            ans+=x\n",
    "            ans%=1e9 + 7 \n",
    "        return int(ans)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        n = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '0':\n",
    "                ans += int(n/2*(1+n))\n",
    "                n = 0\n",
    "            elif s[i] == \"1\":\n",
    "                n += 1\n",
    "        ans += int(n / 2 * (1 + n))\n",
    "        return ans % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        tot,con=0,0\n",
    "        length=len(s)\n",
    "        for i in range(length):\n",
    "            if s[i]==\"0\":\n",
    "                tot+=con*(con+1)//2\n",
    "                con=0\n",
    "            else:\n",
    "                con+=1\n",
    "        tot+=con*(con+1)//2\n",
    "        tot%=(10**9+7)\n",
    "        return tot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        cnt = 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        L = -1\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == \"0\":\n",
    "                cnt = (cnt + (i - L - 1) * (i - L) // 2) % MOD\n",
    "                L = i\n",
    "        return (cnt + (len(s) - L - 1) * (len(s) - L) // 2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        total, temp = 0, 0\n",
    "        length = len(s)\n",
    "        for i in range(length):\n",
    "            if s[i] == '0':\n",
    "                total += temp * (temp + 1) // 2\n",
    "                temp = 0\n",
    "            else:\n",
    "                temp += 1\n",
    "        \n",
    "        total += temp * (temp + 1) // 2\n",
    "        total %= (10**9 + 7)\n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        s = '0'+s\n",
    "        res = 0\n",
    "        tmp = 0\n",
    "        K = 10**9+7\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i]=='0':\n",
    "                res += (tmp+1)*tmp//2\n",
    "                res %= K\n",
    "                tmp = 0\n",
    "            else:\n",
    "                tmp += 1\n",
    "        if tmp>0:\n",
    "            res += (tmp+1)*tmp//2\n",
    "        res %= K\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        mark = []\n",
    "        tmp = 0\n",
    "        for c in s:\n",
    "            if c == '0' and tmp != 0:\n",
    "                mark.append(tmp)\n",
    "                tmp = 0\n",
    "            elif c == '1':\n",
    "                tmp += 1\n",
    "        if tmp != 0: mark.append(tmp)\n",
    "        ans = 0\n",
    "        for num in mark:\n",
    "            ans += (num * (num + 1)) // 2\n",
    "            ans = ans % (1e9 + 7)\n",
    "        return int(ans) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        tmp = []\n",
    "        pre = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '1':\n",
    "                pre += 1\n",
    "            elif pre > 0:\n",
    "                tmp.append(pre)\n",
    "                pre = 0\n",
    "        if pre > 0:\n",
    "            tmp.append(pre)\n",
    "        \n",
    "        # print(tmp)\n",
    "        res = 0\n",
    "        for n in tmp:\n",
    "            res += ((1 + n) * n // 2)\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        result = 0\n",
    "        count = 0\n",
    "        for c in s:\n",
    "            if c == '1':\n",
    "                count += 1\n",
    "                result += count\n",
    "            else:\n",
    "                count = 0\n",
    "        return result % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        cnt = 0\n",
    "        res = 0\n",
    "        for i in s:\n",
    "            if i == '0':\n",
    "                res += (cnt + 1) * cnt // 2\n",
    "                cnt = 0\n",
    "            else:\n",
    "                cnt += 1\n",
    "        else:\n",
    "            res += (cnt + 1) * cnt // 2\n",
    "\n",
    "        return res % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        返回数目 = 0\n",
    "        连续1数量 = 0\n",
    "        for i in s:\n",
    "            if i == \"1\": \n",
    "                连续1数量 += 1\n",
    "                返回数目 += 连续1数量\n",
    "            else:\n",
    "                连续1数量 = 0\n",
    "        return 返回数目%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        one = ans = 0\n",
    "        for c in s:\n",
    "            if c == '1':\n",
    "                one += 1\n",
    "                ans += one\n",
    "            else:\n",
    "                one = 0\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        modd = 10**9+7 \n",
    "        l = 0\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        while l < n:\n",
    "            t = int(s[l])\n",
    "            if t == 1:\n",
    "                r = l\n",
    "                cnt = 0\n",
    "                while r < n and int(s[r]) == 1:\n",
    "                    r += 1\n",
    "                    cnt += 1\n",
    "                ans += (1+cnt)*cnt//2%modd\n",
    "                ans %= modd\n",
    "                l = r\n",
    "            l += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        left,right = 0,0\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        MOD = 10**9+7\n",
    "        while right<n:\n",
    "            if s[left]=='0':\n",
    "                left += 1\n",
    "                right = left\n",
    "            else:\n",
    "                while right<n and s[right]=='1':\n",
    "                    right += 1\n",
    "                ans += (right-left)*(right-left+1)//2\n",
    "                left = right\n",
    "        return ans%MOD\n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        left = 0\n",
    "        right = 0\n",
    "        res = 0\n",
    "        while right < len(s):\n",
    "            while right < len(s) and s[right] != \"1\":\n",
    "                right += 1\n",
    "            left = right\n",
    "            while right < len(s) and s[right] == \"1\":\n",
    "                right += 1\n",
    "            n = right - left\n",
    "            ssum = (1+n)*n//2\n",
    "            res += ssum\n",
    "        return res  % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        total, consecutive = 0, 0\n",
    "        length = len(s)\n",
    "        for i in range(length):\n",
    "            if s[i] == '0':\n",
    "                total += consecutive * (consecutive + 1) // 2\n",
    "                consecutive = 0\n",
    "            else:\n",
    "                consecutive += 1\n",
    "        \n",
    "        total += consecutive * (consecutive + 1) // 2\n",
    "        total %= (10**9 + 7)\n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        i = j = 0\n",
    "        ans = 0\n",
    "        while i < n:\n",
    "            if s[i] == '0': \n",
    "                i += 1\n",
    "                continue\n",
    "            j = i\n",
    "            while j < n and s[j] == '1':\n",
    "                j += 1\n",
    "                ans += j - i\n",
    "            i = j\n",
    "        return ans % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        res = 0\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == '0':\n",
    "                i+=1\n",
    "                continue\n",
    "            n = 0\n",
    "            while i<len(s) and s[i] == '1':\n",
    "                i+=1\n",
    "                n+=1\n",
    "            res+=(n*(n+1))//2\n",
    "        return res %(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        res = 0\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == '0':\n",
    "                i+=1\n",
    "                continue\n",
    "            n = 0\n",
    "            while i<len(s) and s[i] == '1':\n",
    "                i+=1\n",
    "                n+=1\n",
    "            res+=(n*(n+1))//2\n",
    "        return res %(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        mod = 1000000007\n",
    "        ans = 0\n",
    "        acc = 0\n",
    "        for c in s:\n",
    "            if c == '1':\n",
    "                acc += 1\n",
    "                ans += acc\n",
    "            else:\n",
    "                acc = 0\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            j = i\n",
    "            while j < len(s) and s[j] == '1':\n",
    "                j += 1\n",
    "            n = j-i\n",
    "            ans += (1+n)*n // 2\n",
    "            i = j+1\n",
    "        return int(ans % (1e9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        ans=0\n",
    "        x=0\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            if s[i]=='0':\n",
    "                x=0\n",
    "            else:\n",
    "                x+=1\n",
    "            ans+=x\n",
    "        return ans%(10**9+7) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def _numSub(self, s: int) -> int:\n",
    "        return sum(range(1, s+1))\n",
    "\n",
    "    def numSub(self, s: str) -> int:\n",
    "        si = 0\n",
    "        in_range = False\n",
    "        res = 0\n",
    "        for i, x in enumerate(s):\n",
    "            if not in_range and x == '1':\n",
    "                si = i\n",
    "                in_range = True\n",
    "                continue\n",
    "            if in_range and x != '1':\n",
    "                length = (i - si)\n",
    "                res += self._numSub(length)\n",
    "                in_range = False\n",
    "        if in_range:\n",
    "            length = len(s) - si\n",
    "            res += self._numSub(length)\n",
    "        return res % (10**9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        cnt = 0\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if s[i] == \"1\":\n",
    "                left = i\n",
    "                while i + 1 < n and s[i + 1] == \"1\":\n",
    "                    i += 1\n",
    "                cnt = (cnt + (i - left + 1) * (i - left + 2) // 2) % MOD\n",
    "            i += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        t,k = 0,0\n",
    "        length = len(s)\n",
    "        for i in range(length):\n",
    "            if s[i]==\"1\":\n",
    "                k += 1\n",
    "            else:\n",
    "                t += k*(k+1)//2\n",
    "                k = 0\n",
    "        t += k*(k+1)//2\n",
    "        t %=(10**9+7)\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        def count1(i):\n",
    "            return i*(i+1)//2\n",
    "        count=0\n",
    "        zong=0\n",
    "        for i in s:\n",
    "            if i==\"0\":\n",
    "                zong+=count1(count)\n",
    "                count=0\n",
    "            else:\n",
    "                count+=1\n",
    "        zong+=count1(count)\n",
    "        return zong%(10**9+7)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        ans, t = 0, 0\n",
    "        for x in s:\n",
    "            if x == '1':\n",
    "                t += 1\n",
    "                ans += t \n",
    "                ans %= 10**9 + 7\n",
    "            else:\n",
    "                t = 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        result=0\n",
    "        count1=0\n",
    "\n",
    "        for i in s:\n",
    "            if i=='0':\n",
    "                result=result+(count1*(count1+1))//2\n",
    "                count1=0\n",
    "            else:\n",
    "                count1+=1\n",
    "\n",
    "        if i=='1':\n",
    "            result=result+(count1*(count1+1))//2\n",
    "\n",
    "        return result%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "\n",
    "        total, consecutive = 0, 0\n",
    "        length = len(s)\n",
    "\n",
    "        for i in range(length):\n",
    "            if s[i] == '0':\n",
    "                total += consecutive * (consecutive + 1) // 2\n",
    "                consecutive = 0\n",
    "            else:\n",
    "                consecutive += 1\n",
    "        \n",
    "        total += consecutive * (consecutive + 1) // 2\n",
    "        total %= (10**9 + 7)\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        total, consecutive = 0, 0\n",
    "        length = len(s)\n",
    "        for i in range(length):\n",
    "            if s[i] == '0':\n",
    "                total += consecutive * (consecutive + 1) // 2\n",
    "                consecutive = 0\n",
    "            else:\n",
    "                consecutive += 1\n",
    "        \n",
    "        total += consecutive * (consecutive + 1) // 2\n",
    "        total %= (10**9 + 7)\n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        cnt = 0\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if s[i] == \"1\":\n",
    "                left = i\n",
    "                while i + 1 < n and s[i + 1] == \"1\":\n",
    "                    i += 1\n",
    "                cnt = (cnt + (i - left + 1) * (i - left + 2) // 2) % MOD\n",
    "            i += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        res = 0\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == '0':\n",
    "                i+=1\n",
    "                continue\n",
    "            n = 0\n",
    "            while i<len(s) and s[i] == '1':\n",
    "                i+=1\n",
    "                n+=1\n",
    "            res+=(n*(n+1))//2\n",
    "        return res %(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        tmp = 0\n",
    "        res = []\n",
    "        for ch in s:\n",
    "            if ch == '1':\n",
    "                tmp += 1\n",
    "            else:\n",
    "                if tmp:\n",
    "                    res.append(tmp)\n",
    "                tmp = 0\n",
    "        if s[-1] == '1':\n",
    "            res.append(tmp)\n",
    "        ans = 0\n",
    "        for i in res:\n",
    "            ans += (i * (i + 1)) // 2\n",
    "        return ans % mod "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        sum0 = 0\n",
    "        conti = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i]=='1':\n",
    "                conti+=1\n",
    "            if s[i]!='1' or i==len(s)-1:\n",
    "                sum0 = sum0+conti*(conti+1)/2\n",
    "                conti = 0\n",
    "        return int(sum0)%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        s = re.split(\"0+\", s)\n",
    "        for st in s:\n",
    "            if len(st) > 0:\n",
    "                ans += (len(st) + 1) * len(st) // 2      \n",
    "        ans = ans % (10**9 + 7)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        res=0\n",
    "        l=s.split('0')\n",
    "        for tmp in l:\n",
    "            if tmp:\n",
    "                n=len(tmp)\n",
    "                res+=(n+1)*n/2\n",
    "        return int(res%(10**9+7))\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        res = 0\n",
    "        if '1' in s:\n",
    "            s = s.split('0')\n",
    "            for i in s:\n",
    "                n = len(i)\n",
    "                res+=(n+1)*n//2\n",
    "        return res%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        return sum((x+1)*x//2 for x in map(len,s.split('0'))) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        s = s.split('0')\n",
    "        res = 0\n",
    "        mod = 10**9+7\n",
    "        for i in s:\n",
    "            x = len(i)\n",
    "            res += ((1+x)*x//2)%mod\n",
    "            res%=mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        MOD = 1000000007\n",
    "        i, count, ans = 0, 0, 0\n",
    "        while i < len(s):\n",
    "            if s[i] == \"1\":\n",
    "                count += 1\n",
    "            if s[i] == \"0\" :\n",
    "                ans += int((count + 1) * count / 2 )\n",
    "                count = 0\n",
    "            elif  i == len(s) - 1:\n",
    "                ans += int((count + 1) * count / 2 )\n",
    "            i += 1\n",
    "            print(i,\"s\",ans)\n",
    "        return ans  % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        l = len(s)\n",
    "        d = deque(s)\n",
    "        flag = False\n",
    "        s = 0\n",
    "        while d:\n",
    "            temp = d.popleft()\n",
    "            if temp == '0' and flag == False:\n",
    "                continue\n",
    "            elif temp == '0' and flag == True:\n",
    "                ans += s * (s + 1) // 2\n",
    "                s = 0\n",
    "            else:\n",
    "                s += 1\n",
    "                flag = True\n",
    "        return (ans + s * (s + 1) // 2) % (10 ** 9 + 7)\n",
    "\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        def f(n):\n",
    "            return int(n*(n+1)*0.5)\n",
    "        \n",
    "        nums = list(map(str, s.split('0')))\n",
    "        count = 0\n",
    "        for i in range(len(nums)):\n",
    "            count += f(len(nums[i]))\n",
    "        return count % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        list1 = s.split('0')\n",
    "        n = len(list1)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            m = len(list1[i])\n",
    "            res = res + (1 + m)*m/2\n",
    "        return int(res)%(10**(9)+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        res = 0\n",
    "        if '1' in s:\n",
    "            s = s.split('0')\n",
    "            for i in s:\n",
    "                n = len(i)\n",
    "                res+=(n+1)*n//2\n",
    "        return res%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        lst = s.split(\"0\")\n",
    "        res = 0\n",
    "        for ch in lst:\n",
    "            cnt = Counter(ch)\n",
    "            if '1' in ch:\n",
    "                res += (cnt['1'] + 1)*(cnt['1']) // 2\n",
    "        return res % (10 ** 9 + 7)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        MOD = 1000000007\n",
    "        ls = s.split('0')\n",
    "        def leijia(num):\n",
    "            i = 0\n",
    "            for j in range(1, num + 1):\n",
    "                i += j\n",
    "            return i\n",
    "        \n",
    "        res = 0\n",
    "        for i in ls:\n",
    "            res += leijia(len(i))\n",
    "        return res % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        MOD = 1000000007\n",
    "        ls = s.split('0')\n",
    "        def leijia(num):\n",
    "            return int((1 + num)*num/2)\n",
    "        \n",
    "        res = 0\n",
    "        for i in ls:\n",
    "            res += leijia(len(i))\n",
    "        return res % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        MOD = 1000000007\n",
    "        ls = s.split('0')\n",
    "        def leijia(num):\n",
    "            i = 0\n",
    "            for j in range(1, num + 1):\n",
    "                i += j\n",
    "            return i\n",
    "        \n",
    "        res = 0\n",
    "        for i in ls:\n",
    "            res += leijia(len(i))\n",
    "        return res % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        res1 = 0\n",
    "        s = list(s)\n",
    "        if s.count('1') == 0:\n",
    "            return 0\n",
    "        i = s.index('1')\n",
    "        j = i\n",
    "        res = []\n",
    "        while j < len(s) and i < len(s):\n",
    "            if s[i] == '1':\n",
    "                t = 0\n",
    "                while j<len(s):\n",
    "                    if s[j] == '1':\n",
    "                        t+=1\n",
    "                        j+=1\n",
    "                    else:\n",
    "                        break\n",
    "                res.append(t)\n",
    "                i = j\n",
    "            else:\n",
    "                while i < len(s):\n",
    "                    if s[i] != '1':\n",
    "                        i+=1\n",
    "                    else:\n",
    "                        j = i\n",
    "                        break\n",
    "\n",
    "            \n",
    "        for x in res:\n",
    "            res1 += (x+1)*x//2\n",
    "        return res1%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        res1 = 0\n",
    "        s = list(s)\n",
    "        if s.count('1') == 0:\n",
    "            return 0\n",
    "        i = s.index('1')\n",
    "        j = i\n",
    "        res = []\n",
    "        while j < len(s) and i < len(s):\n",
    "            if s[i] == '1':\n",
    "                t = 0\n",
    "                while j<len(s):\n",
    "                    if s[j] == '1':\n",
    "                        t+=1\n",
    "                        j+=1\n",
    "                    else:\n",
    "                        break\n",
    "                res.append(t)\n",
    "                i = j\n",
    "            else:\n",
    "                while i < len(s):\n",
    "                    if s[i] != '1':\n",
    "                        i+=1\n",
    "                    else:\n",
    "                        j = i\n",
    "                        break\n",
    "\n",
    "            \n",
    "        for x in res:\n",
    "            res1 += (x+1)*x//2\n",
    "        return res1%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        res = 0\n",
    "        s = s.split('0')\n",
    "        print(s)\n",
    "        for s_split in s:\n",
    "            length = len(s_split)\n",
    "            if length == 0:\n",
    "                continue\n",
    "            else:\n",
    "                res += ((length + 1) * length // 2)\n",
    "        return res % (10 ** 9 + 7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSub(self, s: str) -> int:\n",
    "        cur=0\n",
    "        r=0\n",
    "        s+='0'\n",
    "        for x in [int(x) for x in s]:\n",
    "            if x:\n",
    "                cur+=1\n",
    "            else:\n",
    "                r += (1+cur)*cur//2\n",
    "                cur=0\n",
    "        return r % 1000000007\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
